FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES

DOI10.1142/S0129054108005875zbMath1155.03022OpenAlexW2061572873MaRDI QIDQ3538855

Victor L. Selivanov

Publication date: 24 November 2008

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054108005875

zbMATH Keywords

Wadge reducibilityWadge degreesWagner hierarchyBüchi-Landweber determinacy

Mathematics Subject Classification ID

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

Related Items (12)

The Wadge Hierarchy of Petri Nets ω-Languages ⋮ Towards a descriptive set theory for domain-like structures ⋮ Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages ⋮ The shrinking property for NP and coNP ⋮ On the main scientific achievements of Victor Selivanov ⋮ Logic vs topology on regular \(\omega \)-languages ⋮ Fine hierarchies via Priestley duality ⋮ Unnamed Item ⋮ LANGUAGES VERSUS ω-LANGUAGES IN REGULAR INFINITE GAMES ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Boolean algebras of regular languages ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words

Cites Work

• First-order logic and star-free sets
• Fine hierarchy of regular \(\omega\)-languages
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Infinite games played on finite graphs
• Topology and descriptive set theory
• A hierarchy of deterministic context-free \(\omega\)-languages.
• Wreath product and infinite words
• The difference and truth-table hierarchies for NP
• On ω-regular sets
• Application of model theoretic games to discrete linear orders and finite automata
• Star-free regular sets of ω-sequences
• Chains and Superchains for ω-Rational Sets, Automata and Semigroups
• Wadge Degrees ofω-Languages of Deterministic Turing Machines
• Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
• Fine hierarchies and Boolean terms
• THE MISSING LINK FOR ω-RATIONAL SETS, AUTOMATA, AND SEMIGROUPS

This page was built for publication: FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES