Structure theory of multi-level deterministically synchronized sequential processes

✍ Scribed by Laura Recalde; Enrique Teruel; Manuel Silva

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 506 KB
• Volume: 254
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(99)00112-7

✦ Synopsis

Multi-level deterministically synchronized sequential processes, or (DS) * SP, is a recursively deÿned modular class of systems. Under interleaving semantics (DS) * SP generalizes free choice (Hack, Master's Thesis, MIT, Cambridge, MA, USA, 1972), equal con ict (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 su cient 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.