|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 3 van 7 gevonden artikelen
| Titel: |
On Recognizable Tree Languages Beyond the Borel Hierarchy |
| Auteur: |
Finkel, Olivier Simonnet, Pierre |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 95 (2009) nr. 2-3 pagina's 287-303 |
| Jaar: |
2009-11-16 |
| Inhoud: |
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 ⩾ 1, there is a D_{ω^n}(Σ^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üchi tree automaton must be Borel. Then we consider the game tree languages W_{(ı,κ)}, for Mostowski-Rabin indices (ıκ). We prove that the D_{ω^n}(Σ^1_1)-complete tree languages L_n are Wadge reducible to the game tree language W_{(ı,κ)} for κ−ı⩾ 2. In particular these languages W_{(ı,κ)} are not in any class D_{α}(Σ^1_1) for α<ω^{ω}. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 3 van 7 gevonden artikelen
| << vorige | volgende >> |