Topological Complexity of Context-Free ω-Languages: A Survey

DOI10.1007/978-3-642-45321-2_4zbMath1486.68095OpenAlexW1869661405MaRDI QIDQ5498741

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

zbMATH Keywords

decision problemstopological complexityBorel hierarchyWadge hierarchyinfinite wordspushdown automatacomplete setsCantor 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)

Related Items (3)

Extending Wagner's hierarchy to deterministic visibly pushdown automata ⋮ On the topological complexity of \(\omega\)-languages of non-deterministic Petri nets ⋮ Input-driven pushdown automata on well-nested infinite strings

This page was built for publication: Topological Complexity of Context-Free ω-Languages: A Survey