On the Length of the Wadge Hierarchy of Omega Context Free Languages

Simple item page
dc.creatorFinkel, Olivier
dc.date2008-01-03
dc.date.accessioned2026-07-07T08:52:21Z
dc.date.available2026-07-07T08:52:21Z
dc.descriptionWe prove in this paper that the length of the Wadge hierarchy of omega context free languages is greater than the Cantor ordinal epsilon_omega, which is the omega-th fixed point of the ordinal exponentiation of base omega. The same result holds for the conciliating Wadge hierarchy, defined by J. Duparc, of infinitary context free languages, studied by D. Beauquier. We show also that there exist some omega context free languages which are Sigma^0_omega-complete Borel sets, improving previous results on omega context free languages and the Borel hierarchy.
dc.identifierhttps://arxiv.org/abs/0801.0534
dc.identifierhttp://arxiv.org/abs/0801.0534
dc.identifierJournal of Automata, Languages and Combinatorics 10 (4) (2005) 439-464
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/145251
dc.subjectLogic in Computer Science
dc.subjectComputational Complexity
dc.subjectComputer Science and Game Theory
dc.subjectLogic
dc.titleOn the Length of the Wadge Hierarchy of Omega Context Free Languages
dc.typetext

Files

Collections

arXiv