2 citations · 3 across the 30 of their papers we have counts for
5 papers · 1 filter
Wadge degrees of omega-powers
Olivier Finkel, Dominique Lecomte
We provide, for each natural number and each class among , and , a regular language whose associated om…
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 …
Decision Problems For Turing Machines
Olivier Finkel, Dominique Lecomte
We answer two questions posed by Castro and Cucker, giving the exact complexities of two decision problems about cardinalities of omega-languages of Turing machines. Firstly, it is…
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…
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…