On the topological complexity of \(\omega\)-languages of non-deterministic Petri nets

DOI10.1016/J.IPL.2013.12.007zbMath1358.68211arXiv1401.6835OpenAlexW2001461320MaRDI QIDQ2446063

Michał Skrzypczak, Olivier Finkel

Publication date: 15 April 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1401.6835

zbMATH Keywords

Petri netstopological complexityformal languagesBorel hierarchyCantor spacecomplete setsBüchi acceptance conditionlanguages of infinite words

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (2)

On the High Complexity of Petri Nets $$\omega $$-Languages ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words

Cites Work

• Lectures on concurrency and Petri nets. Advances in Petri nets.
• Fine hierarchies and m-reducibilities in theoretical computer science
• Wadge reducibility and infinite computations
• Descriptive set theory
• \(X\)-automata on \(\omega\)-words
• \(\omega\)-computations on Turing machines
• Remarks on blind and partially blind one-way multicounter machines
• Infinite behaviour of Petri nets
• Borel ranks and Wadge degrees of context free $\omega$-languages
• The Wadge Hierarchy of Petri Nets ω-Languages
• Topological Complexity of Context-Free ω-Languages: A Survey
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the topological complexity of \(\omega\)-languages of non-deterministic Petri nets