Skip to Main content Skip to Navigation
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.
Complete list of metadata

Cited literature [71 references]  Display  Hide  Download
Contributor : Olivier Finkel Connect in order to contact the contributor
Submitted on : Tuesday, March 12, 2013 - 7:13:40 PM
Last modification on : Thursday, September 29, 2022 - 2:58:07 PM
Long-term archiving on: : Monday, June 17, 2013 - 12:32:54 PM


Files produced by the author(s)


  • HAL Id : ensl-00286373, version 2
  • ARXIV : 0806.1413


Olivier Finkel. Topological Complexity of Context-Free omega-Languages: A Survey. Nachum Dershowitz and Ephraim Nissan. Language, Culture, Computation. Computing - Theory and Technology - Essays Dedicated to Yaacov Choueka on the Occasion of His 75th Birthday, Part I, 8001, Springer, pp.50--77, 2014, Lecture Notes in Computer Science, 978-3-642-45320-5. ⟨ensl-00286373v2⟩



Record views


Files downloads