Complexity of Topological Properties of Regular ω-Languages

DOI10.1007/978-3-540-85780-8_42MaRDI QIDQ3533038zbMATH OpenOpenAlexFDO

Authors Victor Selivanov, K. W. Wagner

Publication date 30 October 2008

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85780-8_42

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Complexity of topological properties of regular \(\omega\)-languages
• Complexity of Aperiodicity for Topological Properties of Regular ω-Languages
• Deciding the topological complexity of Büchi languages
• The Hausdorff-Kuratowski hierarchy of \(\omega\)-regular languages and a hierarchy of Muller automata
• Topological complexity of context-free -languages: a survey

Cites work

• AN ALGEBRAIC THEORY FOR REGULAR LANGUAGES OF FINITE AND INFINITE WORDS
• Chains and Superchains for ω-Rational Sets, Automata and Semigroups
• Computing the Wadge degree, the Lifschitz degree, and the Rabin index of a regular language of infinite words in polynomial time
• Decision problems forω-automata
• Fine hierarchy of regular \(\omega\)-languages
• scientific article; zbMATH DE number 3930351 (Why is no real title available?)
• scientific article; zbMATH DE number 3471986 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• Lower Bounds for Complementation of ω-Automata Via the Full Automata Technique
• On ω-regular sets
• Structural complexity of -automata
• The complementation problem for Büchi automata with applications to temporal logic
• THE MISSING LINK FOR ω-RATIONAL SETS, AUTOMATA, AND SEMIGROUPS

Cited in

(21)

• The Hausdorff-Kuratowski hierarchy of \(\omega\)-regular languages and a hierarchy of Muller automata
• Characterization of -regular languages by monadic second-order formulas
• On the topological complexity of \(\omega\)-languages of non-deterministic Petri nets
• Locally finite -languages and effective analytic sets have the same topological complexity
• The topological complexity of MSO+U and related automata models
• scientific article; zbMATH DE number 5074397 (Why is no real title available?)
• Complexity of topological properties of regular \(\omega\)-languages
• Complexity of Aperiodicity for Topological Properties of Regular ω-Languages
• On the topological complexity of MSO+U and related automata models
• The topological structure of adherences of regular languages
• scientific article; zbMATH DE number 18627 (Why is no real title available?)
• Structural complexity of -automata
• Deciding the topological complexity of Büchi languages
• Refined Bounds on Kolmogorov Complexity for ω-Languages
• Separation property for B- and S-regular languages
• On the Hausdorff measure of regular -languages in Cantor space
• scientific article; zbMATH DE number 2213330 (Why is no real title available?)
• On the main scientific achievements of Victor Selivanov
• A topological property of rational -languages
• The automatic Baire property and an effective property of -rational functions
• Topological complexity of locally finite \(\omega\)-languages

This page was built for publication: Complexity of Topological Properties of Regular ω-Languages

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