Paper Info
Title
On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words
Abstract
We prove that omega-languages of (non-deterministic) Petri nets and omega-languages of (nondeterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of omega-languages of (non-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of !-languages of (non-deterministic) Turing machines. We also show that it is highly undecidable to determine the topological complexity of a Petri net omega-language. Moreover, we infer from the proofs of the above results that the equivalence and the inclusion problems for omega-languages of Petri nets are Pi(1)(2)-complete, hence also highly undecidable. Additionally, we show that the situation is quite the opposite when considering unambiguous Petri nets, which have the semantic property that at most one accepting run exists on every input. We provide a procedure of determinising them into deterministic Muller counter machines with counter copying. As a consequence, we entail that the omega-languages recognisable by unambiguous Petri nets are Delta(0)(3) sets.
Year
DOI
Venue
2021
10.3233/FI-2021-2088
FUNDAMENTA INFORMATICAE
Keywords
DocType
Volume
Automata and formal languages, Petri nets, Infinite words, Logic in computer science, Cantor topology, Borel hierarchy, Wadge degrees, Highly undecidable properties, Unambiguous Petri nets
Journal
183
Issue
ISSN
Citations 
3-4
0169-2968
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Olivier Finkel100.34
Michal Skrzypczak22311.34