An omega-power of a context-free language which is Borel above Delta^0_omega - Archive ouverte HAL Access content directly
Conference Papers Year : 2007

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

(1, 2) , (3)
1
2
3

Abstract

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

Dates and versions

ensl-00147245 , version 1 (16-05-2007)
ensl-00147245 , version 2 (10-01-2008)

Identifiers

Cite

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⟩
340 View
257 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More