10 citations · 57 across the 48 of their papers we have counts for
6 papers · 1 filter
The Determinacy of Context-Free Games
Olivier Finkel
We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter Büchi automata is equivalent to the determinacy of (effective) analytic G…
A Hierarchy of Tree-Automatic Structures
Olivier Finkel, Stevo Todorcevic
We consider -automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of length for some integer $n…
Some Problems in Automata Theory Which Depend on the Models of Set Theory
Olivier Finkel
We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system ZFC. It is known that there are only three possibilities f…
Decision Problems for Recognizable Languages of Infinite Pictures
Olivier Finkel
Altenbernd, Thomas and Wöhrle have considered in [ATW02] acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with the usual acce…
Three Applications to Rational Relations of the High Undecidability of the Infinite Post Correspondence Problem in a Regular omega-Language
Olivier Finkel
It was noticed by Harel in [Har86] that "one can define -complete versions of the well-known Post Correspondence Problem". We first give a complete proof of this result, sho…
Borel Hierarchy and Omega Context Free Languages
Olivier Finkel
We give in this paper additional answers to questions of Lescow and Thomas [Logical Specifications of Infinite Computations, In:"A Decade of Concurrency", Springer LNCS 803 (1994),…