Title: Wadge Degrees of $ω$-Languages of Petri Nets,
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 which also form the class of effective analytic sets. In
particular, for each non-null recursive ordinal $\alpha < \omega\_1^{\rm CK}
$ there exist some ${\bf \Sigma}^0\_\alpha$-complete and some ${\bf
\Pi}^0\_\alpha$-complete $\omega$-languages of Petri nets, and the supremum of
the set of Borel ranks of $\omega$-languages of Petri nets is the ordinal
$\gamma\_2^1$, which is strictly greater than the first non-recursive ordinal
$\omega\_1^{\rm CK}$. We also prove that there are some ${\bf
\Sigma}\_1^1$-complete, hence non-Borel, $\omega$-languages of Petri nets, and
that it is consistent with ZFC that there exist some $\omega$-languages of
Petri nets which are neither Borel nor ${\bf \Sigma}\_1^1$-complete. This
answers the question of the topological complexity of $\omega$-languages of
(non-deterministic) Petri nets which was left open in [DFR14,FS14].