Structure theory of multi-level deterministically synchronized sequential processes

Multi-level deterministically synchronized sequential processes, or (DS)*SP , is a recursively defined modular class of systems. Under interleaving sem antics (DS)*SP generalizes free choice (Hack, Master's Thesis, MIT, Cambrid ge, 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 A utomat. 14(2) (1998) 267-277). Many important results of these subclasses h old also for (DS)*SP. Among them the existence of a polynomial time necessa ry 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 s ubclasses, their interpretation from other points of view, and the realizat ion of what is lost, help to understand which requirements are at the heart of these properties. (C) 2001 Elsevier Science B.V. All rights reserved.