Deciding low levels of tree-automata hierarchy
Igor Walukiewicz · Electronic Notes in Theoretical Computer Science · 2002
The paper concerns hierarchy of indices of finite automata over infinite objects. This hierarchy corresponds exactly to the hierarchy of alternations of least and greatest fixpoints in the mu-calculus. It is also connected to quantifier hierarchies in monadic second-order logic. The open question is to find 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.