Wadge Degrees of $\omega$-Languages of Petri Nets

Olivier Finkel

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 hie…