Topological complexity of context-free -languages: a survey

DOI10.1007/978-3-642-45321-2_4zbMATH Open1486.68095OpenAlexW1869661405MaRDI QIDQ5498741FDOQ5498741

Authors: Olivier Finkel 

Publication date: 10 February 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-45321-2_4

Recommendations

• Topology and ambiguity in \(\omega\)-context free languages
• Borel hierarchy and omega context free languages.
• Topological properties of omega context-free languages
• Wadge hierarchy of omega context-free languages
• New Computational Paradigms

zbMATH Keywords

pushdown automatacomplete setstopological complexityinfinite wordsdecision problemsBorel hierarchyWadge hierarchyCantor topology\(\omega\)-powerscontext-free \(\omega\)-languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive set theory (topological aspects of Borel, analytic, projective, etc. sets) (54H05)

Cited In (11)

• Topological properties of omega context-free languages
• Complexity of topological properties of regular \(\omega\)-languages
• Topology and ambiguity in \(\omega\)-context free languages
• Extending Wagner's hierarchy to deterministic visibly pushdown automata
• On the topological complexity of \(\omega\)-languages of non-deterministic Petri nets
• Locally finite \(\omega\)-languages and effective analytic sets have the same topological complexity
• Complexity of Aperiodicity for Topological Properties of Regular ω-Languages
• Complexity of Topological Properties of Regular ω-Languages
• Topological complexity of locally finite \(\omega\)-languages
• Ambiguity in omega context free languages
• Input-driven pushdown automata on well-nested infinite strings

This page was built for publication: Topological complexity of context-free \(\omega \)-languages: a survey

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