Petri net languages revisited (Q418794)

This paper studies Petri nets behaviour. First it considers atomic nets, i.e., nets with a single place. It shows that the firing sequences of such nets form a context-free language. Next, the commutative languages arising from sequential ones by applying the commutation homomorphism from a monoid of words to a monoid of multisets serve as tools for proving context sensitiveness of the sequential behaviour, regularity of commutative behaviour and decidability of reachability in atomic nets. Finally, these results are lifted to the general case of place/transition nets. It is proved that the sequential behaviour of such nets is the intersection of a finite number of context-free languages and that the commutative behaviour of general nets is regular.