The Wadge Hierarchy of Deterministic Tree Languages

We provide a complete description of the Wadge hierarchy fordeterministically recognisable sets of infinite trees. In particular we give anelementary procedure to decide if one deterministic tree language iscontinuously reducible to another. This extends Wagner's results on thehierarchy of omega-regular languages of words to the case of trees.Comment: 44 pages, 8 figures; extended abstract presented at ICALP 2006, Venice, Italy; full version appears in LMCS special issu