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
Type de document :
Chapitre d'ouvrage
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
Liste complète des métadonnées

Littérature citée [71 références]  Voir  Masquer  Télécharger
https://hal-ens-lyon.archives-ouvertes.fr/ensl-00286373
Contributeur : Olivier Finkel <>
Soumis le : mardi 12 mars 2013 - 19:13:40
Dernière modification le : mardi 24 avril 2018 - 13:52:46
Document(s) archivé(s) le : lundi 17 juin 2013 - 12:32:54

Fichiers

Survey-revised.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Collections

ENS-LYON | INRIA | ELM | LIP | INSMI | UPMC | IMJ | USPC | UNIV-LYON1

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〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

381

Téléchargements de fichiers

139

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD