On the High Complexity of Petri Nets $$\omega $$-Languages

Abstract

We prove that \(\omega \)-languages of (non-deterministic) Petri nets and \(\omega \)-languages of (non-deterministic) 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 \(\omega \)-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 \(\varPi _2^1\)-complete, hence also highly undecidable.