Topological Complexity of Context-Free omega-Languages: A Survey
From MaRDI portal
Publication:6209849
DOI10.1007/978-3-642-45321-2_4zbMATH Open1486.68095arXiv0806.1413MaRDI QIDQ6209849FDOQ6209849
Authors: Olivier Finkel 
Publication date: 9 June 2008
Abstract: We survey recent results on the topological complexity of context-free omega-languages which form the second level of the Chomsky hierarchy of languages of infinite words. In particular, we consider the Borel hierarchy and the Wadge hierarchy of non-deterministic or deterministic context-free omega-languages. We study also decision problems, the links with the notions of ambiguity and of degrees of ambiguity, and the special case of omega-powers.
Formal languages and automata (68Q45) Descriptive set theory (topological aspects of Borel, analytic, projective, etc. sets) (54H05)
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 Q6209849)
