The Wadge hierarchy of Petri nets -languages

MaRDI QIDQ4982345zbMATH OpenFDO

Authors Jacques Duparc, Olivier Finkel, J.-P. Ressayre

Publication date 9 April 2015

zbMATH Keywords

automata theoryBorel hierarchyCantor topologylanguages of infinite wordspartially blind multicounter automataPetri netstopological complexityWadge degreesWadge hierarchy

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Descriptive set theory (03E15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Games involving topology, set theory, or logic (91A44)

Recommendations

• The Wadge hierarchy of Petri nets \(\omega\)-languages
• On the high complexity of Petri nets -languages
• On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
• A hierarchy of deterministic context-free \(\omega\)-languages.
• On the -language expressive power of extended Petri nets

Cited in

(6)

• On the topological complexity of \(\omega\)-languages of non-deterministic Petri nets
• The Wadge hierarchy of Petri nets \(\omega\)-languages
• scientific article; zbMATH DE number 1156490 (Why is no real title available?)
• On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
• On the high complexity of Petri nets -languages
• Polishness of some topologies related to word or tree automata

This page was built for publication: The Wadge hierarchy of Petri nets \(\omega\)-languages

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