An omega-power of a context-free language which is Borel above Delta^0_omega

Jacques Duparc (1, 2) , Olivier Finkel (3)

1 UNIL - Université de Lausanne = University of Lausanne
2 Centre romand en logique, histoire et philosophie des sciences (Western Swiss Center for Logic, History and Philosophy of Sciences)
3 LIP - Laboratoire de l'Informatique du Parallélisme

We use erasers-like basic operations on words to construct a set that is both Borel and above Delta^0_omega, built as a set V^\omega where V is a language of finite words accepted by a pushdown automaton. In particular, this gives a first example of an omega-power of a context free language which is a Borel set of infinite rank.

Mots clés: omega-language; context-free language; omega-power; Cantor topology; topological complexity; Borel hierarchy; Borel ranks; infinite games; Wadge games.; Wadge games

Domaines: Complexité [cs.CC]; Informatique et langage [cs.CL]; Informatique et théorie des jeux [cs.GT]; Logique en informatique [cs.LO]; Logique [math.LO]

Jacques Duparc, Olivier Finkel. An omega-power of a context-free language which is Borel above Delta^0_omega. 2007. ⟨ensl-00147245v1⟩