On the High Complexity of Petri Nets $$\omega $$-Languages
- 30 June 2020
- book chapter
- conference paper
- Published by Springer Science and Business Media LLC
- Vol. 12152, 69-88
- https://doi.org/10.1007/978-3-030-51831-8_4
Abstract
We prove that \(\omega \)-languages of (non-deterministic) Petri nets and \(\omega \)-languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of \(\omega \)-languages of (non-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of \(\omega \)-languages of (non-deterministic) Turing machines. We also show that it is highly undecidable to determine the topological complexity of a Petri net \(\omega \)-language. Moreover, we infer from the proofs of the above results that the equivalence and the inclusion problems for \(\omega \)-languages of Petri nets are \(\varPi _2^1\)-complete, hence also highly undecidable.
Keywords
This publication has 31 references indexed in Scilit:
- Infinite behaviour of deterministic petri netsPublished by Springer Science and Business Media LLC ,2005
- Borel hierarchy and omega context free languagesTheoretical Computer Science, 2003
- A hierarchy of deterministic context-free ω-languagesTheoretical Computer Science, 2003
- An Effective Extension of the Wagner Hierarchy to Blind Counter AutomataLecture Notes in Computer Science, 2001
- Topological properties of omega context-free languagesTheoretical Computer Science, 2001
- Computer science and the fine structure of Borel setsTheoretical Computer Science, 2001
- Wadge hierarchy and Veblen hierarchy Part I: Borel sets of finite rankThe Journal of Symbolic Logic, 2001
- Decidability and complexity of Petri net problems — An introductionLecture Notes in Computer Science, 1998
- X-automata on ω-wordsTheoretical Computer Science, 1993
- ω-Computations on Turing machinesTheoretical Computer Science, 1978