10 citations · 57 across the 48 of their papers we have counts for
52 papers
On the Complexity of the Bi-infinite Post Correspondence Problem
Olivier Finkel, Vesa Halava
In the bi-infinite Post Correspondence Problem (PCP), it is asked whether the same bi-infinite word can be constructed correspondingly from a given finite set of pairs of words…
On Bi-infinite and Conjugate Post Correspondence Problems
Olivier Finkel, Vesa Halava, Tero Harju +1
We study two modifications of the Post Correspondence Problem (PCP), namely 1) the bi-infinite version, where it is asked whether there exists a bi-infinite word such that two give…
On the expressive power of non-deterministic and unambiguous Petri nets over infinite words
Olivier Finkel, Michał Skrzypczak
We prove that -languages of (non-deterministic) Petri nets and -languages of (non-deterministic) Turing machines have the same topological complexity: the Borel and Wadge hie…
Descriptive Set Theory and -Powers of Finitary Languages
Olivier Finkel, Dominique Lecomte
The -power of a finitary language L over a finite alphabet is the language of infinite words over defined by L := {w 0 w 1. .. | i …
Some complete -powers of a one-counter language, for any Borel class of finite rank
Olivier Finkel, Dominique Lecomte
We prove that, for any natural number n 1, we can find a finite alphabet and a finitary language L over accepted by a one-counter automaton, such that the -power L…
An Effective Property of -Rational Functions
Olivier Finkel
We prove that -regular languages accepted by Büchi or Muller automata satisfy an effective automata-theoretic version of the Baire property. Then we use this result to obtain a…