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 metadatas

Cited literature [71 references]  Display  Hide  Download

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 : Wednesday, May 15, 2019 - 3:47:50 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

621

Files downloads

157