Paper Info
Title
The Wadge Hierarchy of Deterministic Tree Languages
Abstract
We provide a complete description of the Wadge hierarchy for deterministi- cally recognisable sets of infinite trees. In particular we give an elementary procedure to decide if one deterministic tree language is continuously reducible to another. This extends Wagner's results on the hierarchy of !-regular languages of words to the case of trees. Two measures of complexity of recognisable languages of infinite words or trees have been considered in literature: the index hierarchy, which reflects the combinatorial com- plexity of the recognising automaton and is closely related to µ-calculus, and the Wadge hierarchy, which is the refinement of the Borel/projective hierarchy that gives the deepest insight into the topological complexity of languages. Klaus Wagner was the first to discover remarkable relations between the two hierarchies for finite-state recognisable (!-regular) sets of infinite words (14). Subsequently, decision procedures determining an !-regular language's position in both hierarchies were given (4, 7, 15). For tree automata the index problem is only solved when the input is a deterministic automaton (9, 13). As for topological complexity of recognisable tree languages, it goes much higher than that of !-regular languages, which are all �03. Indeed, co-Buchi automata over trees may recognise �11-complete languages (8), and Skurczynski (12) proved that there are even weakly recognisable tree languages in every finite level of the Borel hierarchy. This may suggest that in the tree case the topological and combinatorial complexities diverge. On the other hand, the investigations of the Borel/projective hierarchy of deterministic languages (5, 8) reveal some interesting connections with the index hierarchy. Wagner's results (14, 15), giving rise to what is now called the Wagner hierarchy (see (10)), inspire the search for a complete picture of the two hierarchies and the relations between them for recognisable tree languages. In this paper we concentrate on the Wadge hierarchy of deterministic tree languages: we give a full description of the Wadge-equivalence classes forming the hierarchy, together with a procedure calculating the equivalence class
Year
DOI
Venue
2008
10.1007/11787006_35
ICALP'06 Proceedings of the 33rd international conference on Automata, Languages and Programming - Volume Part II
Keywords
DocType
Volume
regular language,borel hierarchy,indexation
Journal
abs/0812.1729
Issue
ISSN
ISBN
4
Logical Methods in Computer Science, Volume 4, Issue 4 (December 23, 2008) lmcs:994
3-540-35907-9
Citations 
PageRank 
References 
13
0.92
11
Authors
2
Name
Order
Citations
PageRank
Filip Murlak118419.14
Michele Bugliesi278572.79