10 citations · 57 across the 48 of their papers we have counts for
30 papers · 1 filter
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 …
Wadge Degrees of -Languages of Petri Nets
Olivier Finkel
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…
On the Topological Complexity of omega-Languages of Non-Deterministic Petri Nets
Olivier Finkel, Michał Skrzypczak
We show that there are -complete languages of infinite words accepted by non-deterministic Petri nets with Büchi acceptance condition, or equivalently by Büchi blind counter…
Infinite Games Specified by 2-Tape Automata
Olivier Finkel
We prove that the determinacy of Gale-Stewart games whose winning sets are infinitary rational relations accepted by 2-tape Büchi automata is equivalent to the determinacy of (effe…
The Determinacy of Context-Free Games
Olivier Finkel
We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter Büchi automata is equivalent to the determinacy of (effective) analytic G…
Ambiguity of ω-Languages of Turing Machines
Olivier Finkel
An ω-language is a set of infinite words over a finite alphabet X. We consider the class of recursive ω-languages, i.e. the class of ω-languages accepted by Turing machines with a…