We study injecti
The third author noticed in his 1992 PhD Thesis [Sim92] that every regular tree language of infinite trees is in a class $Game (D_n({bfSigma}^0_2))$ for some natural number $ngeq 1$, where $Game$ is the game quantifier. We first give a detailed expos
ition of this result. Next, using an embedding of the Wadge hierarchy of non self-dual Borel subsets of the Cantor space $2^omega$ into the class ${bfDelta}^1_2$, and the notions of Wadge degree and Veblen function, we argue that this upper bound on the topological complexity of regular tree languages is much better than the usual ${bfDelta}^1_2$.
We prove that for every Borel equivalence relation $E$, either $E$ is Borel reducible to $mathbb{E}_0$, or the family of Borel equivalence relations incompatible with $E$ has cofinal essential complexity. It follows that if $F$ is a Borel equivalence
relation and $cal F$ is a family of Borel equivalence relations of non-cofinal essential complexity which together satisfy the dichotomy that for every Borel equivalence relation $E$, either $Ein {cal F}$ or $F$ is Borel reducible to $E$, then $cal F$ consists solely of smooth equivalence relations, thus the dichotomy is equivalent to a known theorem.
We study the extension of the Kechris-Solecki-Todorcevic dichotomy on analytic graphs to dimensions higher than 2. We prove that the extension is possible in any dimension, finite or infinite. The original proof works in the case of the finite dimens
ion. We first prove that the natural extension does not work in the case of the infinite dimension, for the notion of continuous homomorphism used in the original theorem. Then we solve the problem in the case of the infinite dimension. Finally, we prove that the natural extension works in the case of the infinite dimension, but for the notion of Baire-measurable homomorphism.
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 of omega-powers available from arXiv:0708.4176) and reflecting also some
open questions which were discussed during the Dagstuhl seminar on Topological and Game-Theoretic Aspects of Infinite Computations 29.06.08 - 04.07.08.
