Abstrakt. Vi undersöker den topologiska komplexiteten hos icke Borel igenkännliga trädspråk med avseende på skillnaden hierarki av analytiska uppsättningar. Vi visar att, för varje heltal n ≥ 1, det finns en D  och 1 )-fullständig trädspråk L n accepteras av en (icke deterministisk) Muller trädautomaton. Å andra sidan bevisar vi att ett trädspråk som accepteras av en entydig Büchi trädautomaton måste vara Borel. Sedan anser vi att spelet träd språk W (ι,σ), för Mostowski-Rabin index (ι, σ). Vi bevisar att D-träd språk L n är Wadge reducible till spelet träd språk W (ι, ) för ί − ι ≥ 2. I synnerhet dessa språk är inte i någon klass D α (1 1 ) för α <.
I REF anser författarna skillnadshierarkin för analytiska uppsättningar.
On Recognizable Tree Languages Beyond the Borel Hierarchy
{'venue': 'Fundamenta Informaticae 95, 2-3 (2009) 287-303', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}