On the Topological Complexity of omega-Languages of Non-Deterministic Petri Nets
classification
💻 cs.LO
cs.CCcs.FL
keywords
netspetriacceptednon-deterministicomega-languagesuchiacceptanceautomata
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.