Topological Complexity of Context-Free omega-Languages: A Survey

Olivier Finkel 1, 2, 3
1 ELM - Équipe de Logique Mathématique
2 IMJ - Institut de Mathématiques de Jussieu
3 LIP - Laboratoire de l'Informatique du Parallélisme
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.
Keywords : decision problems. complete sets Borel hierarchy Wadge hierarchy context-free omega-languages pushdown automata Infinite words decision problems omega-powers topological complexity Cantor topology
Document type :
Book sections
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

Collections

ENS-LYON | INRIA | ELM | LIP | INSMI | UPMC | IMJ | UNIV-LYON1 | SORBONNE-UNIVERSITE | IMJ_LOG | UNIV-PARIS7 | USPC | SU-SCIENCES

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

624

Files downloads

160

Contact

CCSD