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

Simple item page
dc.creatorDuparc, Jacques
dc.creatorFinkel, Olivier
dc.date2008-01-11
dc.date.accessioned2026-07-07T10:01:32Z
dc.date.available2026-07-07T10:01:32Z
dc.descriptionWe 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^ω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.
dc.descriptionTo appear in the Proceedings of the International Conference Foundations of the Formal Sciences V : Infinite Games, November 26th to 29th, 2004, Bonn, Germany, Stefan Bold, Benedikt Löwe, Thoralf Räsch, Johan van Benthem (eds.), College Publications at King's College (Studies in Logic), 2007
dc.identifierhttps://arxiv.org/abs/0801.1783
dc.identifierhttp://arxiv.org/abs/0801.1783
dc.identifierDans Proceedings of the International Conference on Foundations of the Formal Sciences V : Infinite Games - Foundations of the Formal Sciences V : Infinite Games, November 26-29, 2004, Bonn : Allemagne
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/168661
dc.subjectComputational Complexity
dc.subjectComputer Science and Game Theory
dc.subjectLogic in Computer Science
dc.subjectLogic
dc.titleAn omega-power of a context-free language which is Borel above Delta^0_omega
dc.typetext

Files

Collections

arXiv