On the topological complexity of ω-languages of non-deterministic Petri nets

• There are Σ30-complete ω-languages accepted by 1-blind-counter Büchi automata.
• The ω  -languages of deterministic Petri nets are Δ30-sets.
• The ω-languages of non-deterministic Petri nets are more complex than those of deterministic Petri nets.

We show that there are Σ30-complete languages of infinite words accepted by non-deterministic Petri nets with Büchi acceptance condition, or equivalently by Büchi blind counter automata. This shows that ω-languages accepted by non-deterministic Petri nets are topologically more complex than those accepted by deterministic Petri nets.