Topological Complexity of Context-Free omega-Languages: A Survey - Archive ouverte HAL Access content directly
Book Sections Year : 2014

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

(1, 2, 3)
1
2
3

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.
Fichier principal
Vignette du fichier
Survey-revised.pdf (257.83 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

ensl-00286373 , version 1 (09-06-2008)
ensl-00286373 , version 2 (12-03-2013)

Identifiers

Cite

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⟩
441 View
204 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More