On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words
From MaRDI portal
Publication:5025066
DOI10.3233/FI-2021-2088OpenAlexW3179317887MaRDI QIDQ5025066
Michał Skrzypczak, Olivier Finkel
Publication date: 1 February 2022
Published in: Fundamenta Informaticae (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2107.04025
Petri netsBorel hierarchyinfinite wordslogic in computer scienceautomata and formal languagesCantor topologyhighly undecidable propertiesunambiguous Petri netswadge degrees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Choice functions and well-orderings over the infinite binary tree
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- Fine hierarchies and m-reducibilities in theoretical computer science
- Wadge reducibility and infinite computations
- Wadge degrees of infinitary rational relations
- Fine hierarchy of regular \(\omega\)-languages
- Descriptive set theory
- On the reachability problem for 5-dimensional vector addition systems
- Classical recursion theory. The theory of functions and sets of natural numbers
- \(X\)-automata on \(\omega\)-words
- \(\omega\)-computations on Turing machines
- Remarks on blind and partially blind one-way multicounter machines
- Ambiguity in omega context free languages
- A hierarchy of deterministic context-free \(\omega\)-languages.
- Borel hierarchy and omega context free languages.
- Unambiguous Büchi automata.
- Undecidable problems in unreliable computations.
- Topology and ambiguity in \(\omega\)-context free languages
- Büchi VASS recognise \(\mathbf{\Sigma}^{1}_{1}\)-complete \({\omega}\)-languages
- Infinite behaviour of Petri nets
- On the topological complexity of \(\omega\)-languages of non-deterministic Petri nets
- Wadge hierarchy and Veblen hierarchy Part I: Borel sets of finite rank
- Ambiguity of {\omega}-Languages of Turing Machines
- Forms of Determinism for Automata (Invited Talk)
- The Determinacy of Context-Free Games
- On Recognizable Tree Languages Beyond the Borel Hierarchy
- The Complexity of Infinite Computations In Models of Set Theory
- Borel ranks and Wadge degrees of context free $\omega$-languages
- FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES
- Highly Undecidable Problems For Infinite Computations
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- Nondeterministic Ω-Computations and the Analytical Hierarchy
- On ω-regular sets
- Analytic determinacy and 0#
- Π11 Borel sets
- Wadge Degrees ofω-Languages of Deterministic Turing Machines
- Set Theory
- The Containment Problem for Unambiguous Register Automata
- Fine hierarchy of regular ω-languages
- On the High Complexity of Petri Nets $$\omega $$-Languages
- Decision problems forω-automata
- Lectures on Concurrency and Petri Nets
- Computer science and the fine structure of Borel sets
- Topological properties of omega context-free languages
- Wadge hierarchy of omega context-free languages
This page was built for publication: On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words
