1. An omega-power of a context-free language which is Borel above Delta^0_omega
- Author
-
Duparc, Jacques, Finkel, Olivier, Institut d'informatique et organisation (Information Systems Institute) (UNIL), Université de Lausanne = University of Lausanne (UNIL), Centre romand en logique, histoire et philosophie des sciences (Western Swiss Center for Logic, History and Philosophy of Sciences), Université de Lausanne = University of Lausanne (UNIL)-Université de Genève = University of Geneva (UNIGE)-Université de Neuchâtel (UNINE), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Stefan Bold, Benedikt Löwe, Thoralf Räsch, Johan van Benthem, Université de Lausanne (UNIL), Université de Lausanne (UNIL)-University of Geneva [Switzerland]-Université de Neuchâtel (UNINE), and École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL)
- Subjects
FOS: Computer and information sciences ,[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,Computer Science - Logic in Computer Science ,Computational Complexity (cs.CC) ,Borel ranks ,[INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL] ,Topological complexity ,Computer Science - Computer Science and Game Theory ,FOS: Mathematics ,Omega-power ,Wadge games ,[INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT] ,[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,Mathematics - Logic ,Logic in Computer Science (cs.LO) ,Borel hierarchy ,[MATH.MATH-LO]Mathematics [math]/Logic [math.LO] ,Computer Science - Computational Complexity ,Omega-language ,Cantor topology ,Context-free language ,Infinite games ,Logic (math.LO) ,Computer Science::Formal Languages and Automata Theory ,Computer Science and Game Theory (cs.GT) - 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., Comment: To 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\"owe, Thoralf R\"asch, Johan van Benthem (eds.), College Publications at King's College (Studies in Logic), 2007
- Published
- 2008