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

DOI10.1016/J.IPL.2013.12.007MaRDI QIDQ2446063zbMATH OpenOpenAlexFDO

Authors Olivier Finkel, Michał Skrzypczak

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, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.755.6956

zbMATH Keywords

Borel hierarchyBüchi acceptance conditionCantor spacecomplete setsformal languageslanguages of infinite wordsPetri netstopological complexity

Mathematics Subject Classification ID

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

Abstract: We show that there are $Sigm{a}_3^0$-complete languages of infinite words accepted by non-deterministic Petri nets with B"uchi acceptance condition, or equivalently by B"uchi blind counter automata. This shows that omega-languages accepted by non-deterministic Petri nets are topologically more complex than those accepted by deterministic Petri nets.

Recommendations

• On the high complexity of Petri nets -languages
• On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
• The Wadge hierarchy of Petri nets \(\omega\)-languages
• Complexity of Topological Properties of Regular ω-Languages
• The Wadge hierarchy of Petri nets \(\omega\)-languages

Cites work

• -computations on Turing machines
• \(X\)-automata on \(\omega\)-words
• Borel ranks and Wadge degrees of context free \omega-languages
• Descriptive set theory
• Fine hierarchies and m-reducibilities in theoretical computer science
• scientific article; zbMATH DE number 4076638 (Why is no real title available?)
• scientific article; zbMATH DE number 1302047 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 1841831 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• Infinite behaviour of Petri nets
• Lectures on concurrency and Petri nets. Advances in Petri nets.
• Remarks on blind and partially blind one-way multicounter machines
• The Wadge hierarchy of Petri nets \(\omega\)-languages
• Topological complexity of context-free -languages: a survey
• Wadge reducibility and infinite computations

Cited in

(5)

• Büchi VASS recognise \(\mathbf{\Sigma}^{1}_{1}\)-complete \({\omega}\)-languages
• On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
• On the high complexity of Petri nets -languages
• History-deterministic vector addition systems
• Topological complexity of locally finite \(\omega\)-languages

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2446063)