On Recognizable Tree Languages Beyond the Borel Hierarchy

Details On Recognizable Tree Languages Beyond the Borel Hierarchy On Recognizable Tree Languages Beyond the Borel Hierarchy

2009-09-02

arxiv.org/abs/0909.0393v1

Fundamenta Informaticae 95, 2-3 (2009) 287-303

Mathematics

Logic

To appear in Fundamenta Informaticae

Scientific paper

We investigate the topological complexity of non Borel recognizable tree languages with regard to the difference hierarchy of analytic sets. We show that, for each integer $n \geq 1$, there is a $D_{\omega^n}({\bf \Sigma}^1_1)$-complete tree language L_n accepted by a (non deterministic) Muller tree automaton. On the other hand, we prove that a tree language accepted by an unambiguous B\"uchi tree automaton must be Borel. Then we consider the game tree languages $W_{(i,k)}$, for Mostowski-Rabin indices $(i, k)$. We prove that the $D_{\omega^n}({\bf \Sigma}^1_1)$-complete tree languages L_n are Wadge reducible to the game tree language $W_{(i, k)}$ for $k-i \geq 2$. In particular these languages $W_{(i, k)}$ are not in any class $D_{\alpha}({\bf \Sigma}^1_1)$ for $\alpha < \omega^\omega$.

Affiliated with

Also associated with

No associations

Rating

On Recognizable Tree Languages Beyond the Borel Hierarchy does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Recognizable Tree Languages Beyond the Borel Hierarchy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Recognizable Tree Languages Beyond the Borel Hierarchy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-12371