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.
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 : vendredi 16 novembre 2018 - 02:18:33
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

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〉

Partager

Métriques

Consultations de la notice

415

Téléchargements de fichiers

142