On the High Complexity of Petri Nets [Formula: see text]-Languages - Finkel, Olivier (Application and Theory of Petri Nets and Concurrency, 2020)
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.