HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00286373
Contributor : Olivier Finkel Connect in order to contact the contributor
Submitted on : Tuesday, March 12, 2013 - 7:13:40 PM
Last modification on : Saturday, September 11, 2021 - 3:18:17 AM
Long-term archiving on: : Monday, June 17, 2013 - 12:32:54 PM

Files

Survey-revised.pdf
Files produced by the author(s)

Identifiers

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

Citation

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⟩

Share

Metrics

Record views

428

Files downloads

185