On the Topological Complexity of omega-Languages of Non-Deterministic Petri Nets

We show that there are ${\mathrm{\Sigma }}_3^0$-complete languages of infinite words accepted by non-deterministic Petri nets with B"uchi acceptance condition, or equivalently by B"uchi blind counter automata. This shows that omega-languages accepted by non-deterministic Petri nets are topologically more complex than those accepted by deterministic Petri nets.