| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428534 | Information Processing Letters | 2014 | 5 Pages |
Abstract
•There are Σ30-complete ω-languages accepted by 1-blind-counter Büchi automata.•The ω -languages of deterministic Petri nets are Δ30-sets.•The ω-languages of non-deterministic Petri nets are more complex than those of deterministic Petri nets.
We show that there are Σ30-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 ω-languages accepted by non-deterministic Petri nets are topologically more complex than those accepted by deterministic Petri nets.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Olivier Finkel, Michał Skrzypczak,