On the High Complexity of Petri Nets [Formula: see text]-Languages

We prove that [Formula: see text]-languages of (non-deterministic) Petri nets and [Formula: see text]-languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of [Formula: see text]-languages of (non-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of [Formula: see text]-languages of (non-deterministic) Turing machines. We also show that it is highly undecidable to determine the topological complexity of a Petri net [Formula: see text]-language. Moreover, we infer from the proofs of the above results that the equivalence and the inclusion problems for [Formula: see text]-languages of Petri nets are [Formula: see text]-complete, hence also highly undecidable.