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

Olivier Finkel (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

Mots clés: decision problems; Infinite words; pushdown automata; context-free omega-languages; omega-powers; Cantor topology; topological complexity; Borel hierarchy; Wadge hierarchy; complete sets; decision problems.

Domaines: Logique en informatique [cs.LO]; Complexité [cs.CC]; Logique [math.LO]

Olivier Finkel. Topological Complexity of Context-Free omega-Languages: A Survey. 2008. ⟨ensl-00286373v1⟩