zbMATH — the first resource for mathematics

Comparing the expressiveness of timed automata and timed extensions of Petri nets. (English) Zbl 1171.68579
Cassez, Franck (ed.) et al., Formal modeling and analysis of timed systems. 6th international conference, FORMATS 2008, Saint Malo, France, September 15–17, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85777-8/pbk). Lecture Notes in Computer Science 5215, 15-32 (2008).
Summary: Time-dependent models have been intensively studied for many reasons, among others because of their applications in software verification and due to the development of embedded platforms where reliability and safety depend to a large extent on the time features. Many of the time-dependent models were suggested as real-time extensions of several well-known untimed models. The most studied formalisms include Networks of Timed Automata which extend the model of communicating finite-state machines with a finite number of real-valued clocks, and timed extensions of Petri nets where the added time constructs include, e.g., time intervals that are assigned to the transitions (Time Petri Nets) or to the arcs (Timed-Arc Petri Nets). In this paper, we semi-formally introduce these models, discuss their strengths and weaknesses, and provide an overview of the known results about the relationships among the models.
For the entire collection see [Zbl 1149.68007].

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q45 Formal languages and automata
PDF BibTeX Cite
Full Text: DOI