Petri Net Languages and Infinite Subsets of Nm

✍ Scribed by Stéphane Gaubert; Alessandro Giua

• Book ID: 102586499
• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 355 KB
• Volume: 59
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1999.1634

✦ Synopsis

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 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 N m , the class of finite subsets of N m , and the class of ideals (or covering subsets) of N m . 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 N m . 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.