Affiliations: [a] Institut de Mathématiques de Jussieu - Paris Rive Gauche, CNRS, Université de Paris, Sorbonne Université, Paris, France. Olivier.Finkel@math.univ-paris-diderot.fr | [b] Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland. mskrzypczak@mimuw.edu.pl
Correspondence:
[*]
Address for correspondence: CNRS et Universit de Paris, UFR de Mathématiques case 7012, 75205 Paris Cedex 13, France
Note: [†] Author supported by Polish National Science Centre grant 2016/22/E/ST6/00041.
Abstract: We prove that ω-languages of (non-deterministic) Petri nets and ω-languages of (nondeterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of ω-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 ω-language. Moreover, we infer from the proofs of the above results that the equivalence and the inclusion problems for ω-languages of Petri nets are ∏21-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 ω-languages recognisable by unambiguous Petri nets are △30 sets.
Keywords: Automata and formal languages, Petri nets, Infinite words, Logic in computer science, Cantor topology, Borel hierarchy, Wadge degrees, Highly undecidable properties, Unambiguous Petri nets
