Structure theory of multi-level deterministically synchronized sequential processes

AbstractMulti-level deterministically synchronized sequential processes, or (DS)∗SP, is a recursively defined modular class of systems. Under interleaving semantics (DS)∗SP generalizes free choice (Hack, Master's Thesis, MIT, Cambridge, MA, USA, 1972), equal conflict (Teruel and Silva, Theoret. Comput. Sci. 153 (1–2) (1996) 271–300), or DSSP (Recalde et al., IEEE Trans. Robotics Automat. 14(2) (1998) 267–277). Many important results of these subclasses hold also for (DS)∗SP. Among them the existence of a polynomial time necessary and sufficient condition for the existence of a live and bounded marking. The extension to (DS)∗SP of results that were known for more restricted subclasses, their interpretation from other points of view, and the realization of what is lost, help to understand which requirements are at the heart of these properties