 |
 |
 |
 |
Book sections
Topological Complexity of Context-Free omega-Languages: A Survey
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.
Cited literature [71 references]
https://hal-ens-lyon.archives-ouvertes.fr/ensl-00286373
Contributor : Olivier Finkel <>
Submitted on : Tuesday, March 12, 2013 - 7:13:40 PM
Last modification on : Thursday, December 10, 2020 - 10:54:58 AM
Long-term archiving on: : Monday, June 17, 2013 - 12:32:54 PM
Contributor : Olivier Finkel <>
Submitted on : Tuesday, March 12, 2013 - 7:13:40 PM
Last modification on : Thursday, December 10, 2020 - 10:54:58 AM
Long-term archiving on: : Monday, June 17, 2013 - 12:32:54 PM
Files
Survey-revised.pdf
Files produced by the author(s)