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 considering the classes of semi-cylindrical, star-free, recognizable, rational (or semilinear) 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 semilinear 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 solvable. We establish as intermediate results some properties of star-free subsets of general monoids.