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].
Download