10 citations · 57 across the 48 of their papers we have counts for
13 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…
Topological Complexity of Context-Free omega-Languages: A Survey
Olivier Finkel
We survey recent results on the topological complexity of context-free omega-languages which form the second level of the Chomsky hierarchy of languages of infinite words. In parti…
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…