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

Abstract

We show that there are ${\Sigma }_3^0$-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 omega-languages accepted by non-deterministic Petri nets are topologically more complex than those accepted by deterministic Petri nets.