Petri net languages and infinite subsets of Nm

Families of Petri net languages are usually defined by varying the type of transition labeling and the class of subsets of Nm to be used as sets of final markings (m is the number of places). So far three main classes of subsets have been studied: the trivial class containing as single element Nm, the class of finite subsets of Nm, and the class of ideals (or covering subsets) of Nm. In this paper we extend the known hierarchy of Petri net languages by consider-ing the classes of semi-cylindrical, star-free, recognizable, rational (or semi-linear) subsets of Nm. We compare the related Petri net languages. For arbitrarily labeled and for *-free labeled Petri net languages, the above hierarchy collapses: one does not increase the generality by considering semi-linear accepting sets instead of the usual finite ones. However, for free-labeled and for deterministic Petri net languages, we show that one gets new distinct subclasses of languages, for which several decidability problems become solv-able. We establish as intermediate results some properties of star-free subsets of general monoids. 1999 Academic Press 1