A hierarchy of deterministic context-free -languages.

DOI10.1016/S0304-3975(02)00567-4MaRDI QIDQ1401159zbMATH OpenFDO

Authors Jacques Duparc

Publication date 17 August 2003

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

Full work available at URL https://doi.org/10.1016/S0304-3975(02)00567-4

zbMATH Keywords

Deterministic context-free \(\omega\)-languagesPushdown automataWadge hierarchy

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Wadge hierarchy of omega context-free languages
• New Computational Paradigms
• The Wadge-Wagner hierarchy of ω-rational sets
• On the length of the Wadge hierarchy of -context-free languages
• The Wadge Hierarchy of Deterministic Tree Languages

Cites work

• -computations on deterministic pushdown machines
• Borel determinacy
• Computer science and the fine structure of Borel sets
• Descriptive set theory
• Deterministic context free languages
• scientific article; zbMATH DE number 3849219 (Why is no real title available?)
• scientific article; zbMATH DE number 4061224 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• On ω-regular sets
• Separation principles and the axiom of determinateness
• Solving Sequential Conditions by Finite-State Strategies
• Theory of -languages. I: Characterizations of -context- free languages
• Topological properties of omega context-free languages
• Topology and descriptive set theory
• Wadge hierarchy and Veblen hierarchy. I: Borel sets of finite rank

Cited in

(30)

• Ambiguity in omega context free languages
• Borel hierarchy and omega context free languages.
• On omega context free languages which are Borel sets of infinite rank.
• Logic for \(\omega\)-pushdown automata
• Wadge-Wagner hierarchies
• Input-driven pushdown automata on well-nested infinite strings
• Locally finite -languages and effective analytic sets have the same topological complexity
• The Wadge hierarchy of Petri nets \(\omega\)-languages
• The Algebraic Counterpart of the Wagner Hierarchy
• FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES
• Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata
• Wadge Degrees ofω-Languages of Deterministic Turing Machines
• THE WAGNER HIERARCHY
• The Wadge hierarchy of Petri nets \(\omega\)-languages
• On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
• On the high complexity of Petri nets -languages
• Baire reductions and good Borel reducibilities
• A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : Part I
• A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy : Part II
• scientific article; zbMATH DE number 6764298 (Why is no real title available?)
• The determinacy strength of pushdownω-languages
• THE MISSING LINK FOR ω-RATIONAL SETS, AUTOMATA, AND SEMIGROUPS
• The Wadge Hierarchy of Deterministic Tree Languages
• The Wadge Hierarchy of Deterministic Tree Languages
• Topological properties of omega context-free languages
• Wadge hierarchy of omega context-free languages
• scientific article; zbMATH DE number 7770056 (Why is no real title available?)
• Extending Wagner's hierarchy to deterministic visibly pushdown automata
• Towards a descriptive set theory for domain-like structures
• Fine hierarchies and m-reducibilities in theoretical computer science

This page was built for publication: A hierarchy of deterministic context-free \(\omega\)-languages.

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