@article{Walukiewicz:ENTCS:2002,
    Abstract = {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.},
    Author = {Walukiewicz, Igor},
    File = {Deciding low levels of tree-automata hierarchy - igw-wollic - a - i.pdf},
    ISSN = {1571-0661},
    Journal = {Electronic Notes in Theoretical Computer Science},
    Keywords = {finite automata, quantifier hierarchy, mu-calculus, fixpoint},
    Note = {WoLLIC'2002, 9th Workhop on Logic, Language, Information and Computation},
    Pages = {61--75},
    Title = {Deciding low levels of tree-automata hierarchy},
    URL = {http://www.sciencedirect.com/science/article/pii/S1571066104805413},
    Volume = {67},
    Year = {2002},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S1571066104805413},
    bdsk-url-2 = {https://doi.org/10.1016/S1571-0661(04)80541-3},
    date-added = {2020-08-04 12:29:46 +0200},
    date-modified = {2020-08-11 12:18:54 +0200},
    doi = {10.1016/S1571-0661(04)80541-3}
}

@article{Walukiewicz:ENTCS:2002, Abstract = {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.}, Author = {Walukiewicz, Igor}, File = {Deciding low levels of tree-automata hierarchy - igw-wollic - a - i.pdf}, ISSN = {1571-0661}, Journal = {Electronic Notes in Theoretical Computer Science}, Keywords = {finite automata, quantifier hierarchy, mu-calculus, fixpoint}, Note = {WoLLIC'2002, 9th Workhop on Logic, Language, Information and Computation}, Pages = {61--75}, Title = {Deciding low levels of tree-automata hierarchy}, URL = {http://www.sciencedirect.com/science/article/pii/S1571066104805413}, Volume = {67}, Year = {2002}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S1571066104805413}, bdsk-url-2 = {https://doi.org/10.1016/S1571-0661(04)80541-3}, date-added = {2020-08-04 12:29:46 +0200}, date-modified = {2020-08-11 12:18:54 +0200}, doi = {10.1016/S1571-0661(04)80541-3} }