WoLLIC 2002 Preliminary Version Deciding low levels of tree-automata hierarchy

The paper discusses the hierarchy of indices of nite automata over innite objects. This hierarchy corresponds exactly to the hierarchy of alternations of least and greatest xpoints in the mu-calculus. It is also connected to quantier hierarchies in monadic second-order logic. The open question is to nd a procedure that given a regular tree language decides its level in the index hierarchy. Here, decision procedures are presented for low levels of the hierarchy. It is shown that these procedures have optimal complexity.