10 citations · 57 across the 48 of their papers we have counts for
7 papers · 1 filter
On Some Sets of Dictionaries Whose omega-Powers Have a Given Complexity
Olivier Finkel
A dictionary is a set of finite words over some finite alphabet X. The omega-power of a dictionary V is the set of infinite words obtained by infinite concatenation of words in V.…
The Complexity of Infinite Computations In Models of Set Theory
Olivier Finkel
We prove the following surprising result: there exist a 1-counter Büchi automaton and a 2-tape Büchi automaton such that the ω-language of the first and the infinitary rational rel…
Decision Problems For Turing Machines
Olivier Finkel, Dominique Lecomte
We answer two questions posed by Castro and Cucker, giving the exact complexities of two decision problems about cardinalities of omega-languages of Turing machines. Firstly, it is…
On Recognizable Tree Languages Beyond the Borel Hierarchy
Olivier Finkel, Pierre Simonnet
We investigate the topological complexity of non Borel recognizable tree languages with regard to the difference hierarchy of analytic sets. We show that, for each integer $n \geq…
On Decidability Properties of One-Dimensional Cellular Automata
Olivier Finkel
In a recent paper Sutner proved that the first-order theory of the phase-space of a one-dimensional cellular automaton $\m…
On Recognizable Languages of Infinite Pictures
Olivier Finkel
In a recent paper, Altenbernd, Thomas and Wöhrle have considered acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with the us…