Petri net languages and infinite subsets of N-m

Families of Petri net languages are usually defined by varying the type of transition labeling and the class of subsets of N-m to be used as sets of f inal markings (m is the number of places). So far three main classes of sub sets have been studied: the trivial class containing as single element N-m: the class of finite subsets of N-m, and the class of ideals (or covering s ubsets) of N-m. In this paper we extend the known hierarchy of Petri net la nguages by considering the classes of semi-cylindrical, star-free, recogniz able, rational (or semilinear) subsets of N-m. We compare the related Petri net languages. For arbitrarily labeled and for lambda-free labeled Petri n et languages, the above hierarchy collapses: one does not increase the gene rality 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 seve ral decidability problems become solvable. We establish as intermediate res ults some properties of star-free subsets Of general monoids. (C) 1999 Acad emic Press.