Wadge Degrees of ω-Languages of Petri Nets
share
We prove that ω-languages of (non-deterministic) Petri nets and ω-languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of ω-languages of (non-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of ω-languages of (non-deterministic) Turing machines which also form the class of effective analytic sets. In particular, for each non-null recursive ordinal α < ω_1^ CK there exist some Σ^0_α-complete and some Π^0_α-complete ω-languages of Petri nets, and the supremum of the set of Borel ranks of ω-languages of Petri nets is the ordinal γ_2^1, which is strictly greater than the first non-recursive ordinal ω_1^ CK. We also prove that there are some Σ_1^1-complete, hence non-Borel, ω-languages of Petri nets, and that it is consistent with ZFC that there exist some ω-languages of Petri nets which are neither Borel nor Σ_1^1-complete. This answers the question of the topological complexity of ω-languages of (non-deterministic) Petri nets which was left open in [DFR14,FS14].
READ FULL TEXT