3 citations · 9 across the 23 of their papers we have counts for
7 papers · 1 filter
Undecidable Problems About Timed Automata
Olivier Finkel
We solve some decision problems for timed automata which were recently raised by S. Tripakis in [ Folk Theorems on the Determinization and Minimization of Timed Automata, in the Pr…
Borel Ranks and Wadge Degrees of Context Free Omega Languages
Olivier Finkel
We show that, from a topological point of view, considering the Borel and the Wadge hierarchies, 1-counter Büchi automata have the same accepting power than Turing machines equippe…
On the Accepting Power of 2-Tape Büchi Automata
Olivier Finkel
We show that, from a topological point of view, 2-tape Büchi automata have the same accepting power than Turing machines equipped with a Büchi acceptance condition. In particular,…
On Decidability Properties of Local Sentences
Olivier Finkel
Local (first order) sentences, introduced by Ressayre, enjoy very nice decidability properties, following from some stretching theorems stating some remarkable links between the fi…
Classical and Effective Descriptive Complexities of omega-Powers
Olivier Finkel, Dominique Lecomte
We prove that, for each non null countable ordinal alpha, there exist some Sigma^0_alpha-complete omega-powers, and some Pi^0_alpha-complete omega-powers, extending previous works…
There Exist some Omega-Powers of Any Borel Rank
Dominique Lecomte, Olivier Finkel
Omega-powers of finitary languages are languages of infinite words (omega-languages) in the form V^omega, where V is a finitary language over a finite alphabet X. They appear very…