Computer science and the fine structure of Borel sets

DOI10.1016/S0304-3975(00)00111-0MaRDI QIDQ5941255zbMATH OpenWikidataFDO

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

Publication date 20 August 2001

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(00)00111-0

zbMATH Keywords

Borel hierarchyBüchi automataeffective determinacynon Borel sets of infinite sequencespush-down automatatransfinite wordsWadge hierarchy

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Descriptive set theory (03E15) Formal languages and automata (68Q45)

Recommendations

• Borel ranks and Wadge degrees of context free \omega-languages
• The Wadge Hierarchy of Deterministic Tree Languages
• Wadge Degrees ofω-Languages of Deterministic Turing Machines
• New Computational Paradigms
• scientific article; zbMATH DE number 3849219

Cites work

• Borel determinacy
• Formal languages defined by the underlying structure of their words
• Functors and ordinal notations. I: A functorial construction of the veblen hierarchy
• scientific article; zbMATH DE number 3849219 (Why is no real title available?)
• scientific article; zbMATH DE number 4139726 (Why is no real title available?)
• scientific article; zbMATH DE number 4061224 (Why is no real title available?)
• scientific article; zbMATH DE number 3993574 (Why is no real title available?)
• scientific article; zbMATH DE number 819382 (Why is no real title available?)
• Les propriétés de réduction et de norme pour les classes de Boréliens
• Locally finite languages
• On ω-regular sets
• Stretchings
• The monadic second-order logic of graphs. IX: Machines and their behaviours
• The monadic second-order logic of graphs. X: Linear orderings
• Wadge hierarchy and Veblen hierarchy. I: Borel sets of finite rank

Cited in

(17)

• Ambiguity in omega context free languages
• A hierarchy of deterministic context-free \(\omega\)-languages.
• Borel hierarchy and omega context free languages.
• On omega context free languages which are Borel sets of infinite rank.
• Descriptive set theory, from Cantor to Wadge and beyond
• Locally finite -languages and effective analytic sets have the same topological complexity
• The Wadge hierarchy of Petri nets \(\omega\)-languages
• ON RECOGNIZABLE LANGUAGES OF INFINITE PICTURES
• On the Topological Complexity of Infinitary Rational Relations
• On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
• On the high complexity of Petri nets -languages
• A hierarchy of tree-automatic structures
• Weak arithmetics
• Weak arithmetic
• Topological properties of omega context-free languages
• Wadge hierarchy of omega context-free languages
• Topological complexity of locally finite \(\omega\)-languages

This page was built for publication: Computer science and the fine structure of Borel sets

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