HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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

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.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00147245
Contributor : Olivier Finkel Connect in order to contact the contributor
Submitted on : Thursday, January 10, 2008 - 6:12:18 PM
Last modification on : Saturday, September 11, 2021 - 3:16:51 AM
Long-term archiving on: : Friday, November 25, 2016 - 8:17:32 PM

Files

paper-FotFS-2004.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : ensl-00147245, version 2
  • ARXIV : 0801.1783

Collections

Citation

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⟩

Share

Metrics

Record views

335

Files downloads

245