Dominique Lecomte
Potential Wadge classes.
Втр, 02/09/2010 - 16:01 — SomNambulAuthors: Dominique Lecomte
Subjects: Logic
AbstractLet $\bf\Gamma$ be a Borel class, or a Wadge class of Borel sets, and $2\leq
d\leq\omega$ a cardinal. We study the Borel subsets of ${\mathbb R}^d$ that can
be made $\bf\Gamma$ by refining the Polish topology on the real line. These
sets are called potentially $\bf\Gamma$. We give a test to recognize
potentially $\bf\Gamma$ sets.Decision Problems For Turing Machines.
Пт, 09/04/2009 - 12:10 — SomNambulAuthors: Olivier Finkel, Dominique Lecomte
Subjects: Logic in Computer Science
AbstractWe 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 $D_2(\Sigma_1^1)$-complete to determine whether
the omega-language of a given Turing machine is countably infinite, where
$D_2(\Sigma_1^1)$ is the class of 2-differences of $\Sigma_1^1$-sets. Secondly,
it is $\Sigma_1^1$-complete to determine whether the omega-language of a given
Turing machine is uncountable.
Вход в систему
