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

Olivier Finkel

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

Olivier Finkel ^{1, 2, 3}

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

Domain :

Computer Science [cs] / Logic in Computer Science [cs.LO]

Computer Science [cs] / Computational Complexity [cs.CC]

Mathematics [math] / Logic [math.LO]

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

Survey-revised.pdf

Files produced by the author(s)

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

Files

Identifiers

Collections

Citation

Export

Metrics

621

157

Contact

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

Files

Identifiers

Collections

Citation

Export

Share

Metrics

621

157

Contact