3 citations · 9 across the 23 of their papers we have counts for
12 papers · 1 filter
Highly Undecidable Problems about Recognizability by Tiling Systems
Olivier Finkel
Altenbernd, Thomas and Wöhrle have considered acceptance of languages of infinite two-dimensional words (infinite pictures) by finite tiling systems, with usual acceptance conditio…
Topological Complexity of omega-Powers : Extended Abstract
Olivier Finkel, Dominique Lecomte
This is an extended abstract presenting new results on the topological complexity of omega-powers (which are included in a paper "Classical and effective descriptive complexities o…
Wadge Degrees of Infinitary Rational Relations
Olivier Finkel
We show that, from the topological point of view, 2-tape Büchi automata have the same accepting power as Turing machines equipped with a Büchi acceptance condition. The Borel and t…
Closure Properties of Locally Finite Omega Languages
Olivier Finkel
Locally finite omega languages were introduced by Ressayre in [Journal of Symbolic Logic, Volume 53, No. 4, p.1009-1026]. They generalize omega languages accepted by finite automat…
On the Topological Complexity of Infinitary Rational Relations
Olivier Finkel
We prove in this paper that there exists some infinitary rational relations which are analytic but non Borel sets, giving an answer to a question of Simonnet [Automates et Théorie…
On Winning Conditions of High Borel Complexity in Pushdown Games
Olivier Finkel
Some decidable winning conditions of arbitrarily high finite Borel complexity for games on finite graphs or on pushdown graphs have been recently presented by O. Serre in [ Games w…