On the Topological Complexity of omega-Languages of Non-Deterministic   Petri Nets
  We show that there are $\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. 
Olivier Finkel (ELM, IMJ), Micha{\l} Skrzypczak
cs.LO cs.CC cs.FL