# On the expressive power of non-deterministic and unambiguous Petri nets over infinite words

@article{Finkel2021OnTE, title={On the expressive power of non-deterministic and unambiguous Petri nets over infinite words}, author={O. Finkel and Michal Skrzypczak}, journal={ArXiv}, year={2021}, volume={abs/2107.04025} }

We prove that ω-languages of (non-deterministic) Petri nets and ωlanguages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of ωlanguages of (non-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of ω-languages of (non-deterministic) Turing machines. We also show that it is highly undecidable to determine the topological complexity of a Petri net ω-language. Moreover, we infer from the… Expand

#### References

SHOWING 1-10 OF 63 REFERENCES

Wadge Degrees of ω-Languages of Petri Nets

- Computer Science, Mathematics
- ArXiv
- 2017

It is proved that the Borel and Wadge hierarchies of the class of ω-languages of (non-deterministic) Petri nets are equal to the Borels and Wadges of theclass of ϊ-l languages of ( non-determinist) Turing machines, and that there are some Σ1-complete, hence non-Borel, ψ-l Languages of Petrinets. Expand

On the High Complexity of Petri Nets ømega-Languages

- Computer Science, Mathematics
- Petri Nets
- 2020

It is proved that the Borel and Wadge hierarchies of the class of \(\omega \)-languages of Petri nets and of (non-deterministic) Turing machines have the same topological complexity. Expand

On the Topological Complexity of MSO+U and Related Automata Models

- Computer Science, Mathematics
- MFCS
- 2010

This work shows that for each i ∈ ω there exists a $\Sigma ^1_i$-hard ω-word language definable in Monadic Second Order Logic extended with the unbounding quantifier (MSO+U), and solves the topological complexity of MSO+ U. Expand

Topological properties of omega context-free languages

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2001

It is shown that Buchi–Landweber's Theorem cannot be extended to even closed ω - CFL : in a Gale–Stewart game with a (closed) ω- CFL winning set, one cannot decide which player has a winning strategy. Expand

On the topological complexity of ω-languages of non-deterministic Petri nets

- Mathematics, Computer Science
- Inf. Process. Lett.
- 2014

We show that there are @S"3^0-complete languages of infinite words accepted by non-deterministic Petri nets with Buchi acceptance condition, or equivalently by Buchi blind counter automata. This… Expand

On Büchi One-Counter Automata

- Mathematics, Computer Science
- STACS
- 2017

The first result shows that decidability no longer holds when moving from finite words to infinite words and proves that already the equivalence problem for deterministic Buchi one-counter automata is undecidable. Expand

Borel hierarchy and omega context free languages

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2003

This paper proves topological properties of omega context free languages (�-CFL) which extend those of O. Finkel (Theoret. Expand

The Wadge Hierarchy of Petri Nets ω-Languages

- Mathematics, Computer Science
- LFCS
- 2013

The Wadge hierarchy of the ω-languages recognized by deterministic Petri nets is described, and it is shown that the whole hierarchy has height \(\omega^{\omega^{2}\), and the restrictions of this hierarchy to every fixed number of partially blind counters are given. Expand

Automata on Infinite Objects

- Computer Science, Mathematics
- Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics
- 1990

This chapter discusses the formulation of two interesting generalizations of Rabin's Tree Theorem and presents some remarks on the undecidable extensions of the monadic theory of the binary tree. Expand

The determinacy of context-free games

- Mathematics, Computer Science
- J. Symb. Log.
- 2013

We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter Buchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games… Expand