3 citations · 9 across the 23 of their papers we have counts for
4 papers · 1 filter
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 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…
Highly Undecidable Problems For Infinite Computations
Olivier Finkel
We show that many classical decision problems about 1-counter omega-languages, context free omega-languages, or infinitary rational relations, are -complete, hence located a…