On the topological complexity of ?-languages of non-deterministic Petri nets
There are ? 3 0 -complete ?-languages accepted by 1-blind-counter Bchi automata. The ? -languages of deterministic Petri nets are ? 3 0 -sets. The ?-languages of non-deterministic Petri nets are more complex than those of deterministic Petri nets.
topological complexity petri nets formal languages languages of infinite words bchi acceptance condition cantor space borel hierarchy complete sets