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
pushdown automatacomplete setstopological complexityinfinite wordsdecision problemsBorel hierarchyWadge hierarchyCantor topology\(\omega\)-powerscontext-free \(\omega\)-languages
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)