Petri net languages revisited

In this paper, the behavior of place/transition Petri nets is discussed. As a formal tool of consideration a commutation homomorphism of monoids is applied, which gives rise to a comparison of the sequential behavior of nets with its commutative version. The sequential and commutative languages are discussed and compared by means of commutation homomorphism from the monoid of words to the monoid of multisets. First, atomic nets (nets with a single place only) are considered. It is proved that (1) the sequential behavior of atomic nets is a context free language, and (2) the commutative behavior, obtained as a homomorphic image of the sequential one, is regular. From here, via compositionality property of nets these results are lifted to the case of all place/transition nets. Namely, it turns out that the sequential behavior of any Petri net is the intersection of a finite number of context free languages, and next, that commutative behavior of any general net is regular. The substantial part in the presented approach plays reduced languages, as a “go between”: they are regular subsets of sequential languages of nets with the same commutative images as the original ones.