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: Wadge games.; Omega-language; Context-free language; Omega-power; Cantor topology; Topological complexity; Borel hierarchy; Borel ranks; Infinite 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. Foundations of the Formal Sciences V : Infinite Games, November 26-29, 2004, Bonn, Germany. pp.109-122. ⟨ensl-00147245v2⟩