A trace semantics for Petri nets. (English) Zbl 0826.68085

Hoogers, P. W.; Kleijn, H. C. M.; Thiagarajan, P. S.

Inf. Comput. 117, No. 1, 98-114 (1995).

Summary: A generalization of the notion of trace is proposed. This enables us to associate with each Petri net a single behavioural object, namely a poset of (generalized) traces. A generalization is given of the trace languages defined by Petri nets. We show that the general event structures of Winskel and the stable event structures can also be characterized in terms of our trace languages. One consequence is that in this framework, stable event structures, general event structures, and Petri nets constitute a strictly ascending chain in terms of expressive power.

MSC:

68Q85	Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q55	Semantics in the theory of computing
68Q45	Formal languages and automata

Keywords:

Petri nets