@article{NiwinskiWalukiewicz:TCS:2003,
    Abstract = {We show that a tree language recognized by a deterministic parity automaton is either hard for the co-B{\"u}chi level and therefore cannot be recognized by a weak alternating automaton, or is on a very low level in the hierarchy of weak alternating automata. A topological counterpart of this property is that a deterministic tree language is either Π11 complete (and hence nonBorel), or it is on the level Π30 of the Borel hierarchy. We also give a new simple proof of the strictness of the hierarchy of weak alternating automata.},
    Author = {Niwi{\'n}ski, Damian and Walukiewicz, Igor},
    File = {A gap property of deterministic tree languages - 1-s2.0-S0304397502004528-main - a - a - a - f.pdf},
    ISSN = {0304-3975},
    Journal = {Theoretical Computer Science},
    Number = {1},
    Pages = {215--231},
    Title = {A gap property of deterministic tree languages},
    URL = {http://www.sciencedirect.com/science/article/pii/S0304397502004528},
    Volume = {303},
    Year = {2003},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0304397502004528},
    bdsk-url-2 = {https://doi.org/10.1016/S0304-3975(02)00452-8},
    date-added = {2020-01-18 17:16:14 +0100},
    date-modified = {2020-08-12 14:58:01 +0200},
    file-2 = {A gap property of deterministic tree languages - igw-gap - a - a - a - f.pdf},
    doi = {10.1016/S0304-3975(02)00452-8}
}

@article{NiwinskiWalukiewicz:TCS:2003, Abstract = {We show that a tree language recognized by a deterministic parity automaton is either hard for the co-B{\"u}chi level and therefore cannot be recognized by a weak alternating automaton, or is on a very low level in the hierarchy of weak alternating automata. A topological counterpart of this property is that a deterministic tree language is either Π11 complete (and hence nonBorel), or it is on the level Π30 of the Borel hierarchy. We also give a new simple proof of the strictness of the hierarchy of weak alternating automata.}, Author = {Niwi{\'n}ski, Damian and Walukiewicz, Igor}, File = {A gap property of deterministic tree languages - 1-s2.0-S0304397502004528-main - a - a - a - f.pdf}, ISSN = {0304-3975}, Journal = {Theoretical Computer Science}, Number = {1}, Pages = {215--231}, Title = {A gap property of deterministic tree languages}, URL = {http://www.sciencedirect.com/science/article/pii/S0304397502004528}, Volume = {303}, Year = {2003}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0304397502004528}, bdsk-url-2 = {https://doi.org/10.1016/S0304-3975(02)00452-8}, date-added = {2020-01-18 17:16:14 +0100}, date-modified = {2020-08-12 14:58:01 +0200}, file-2 = {A gap property of deterministic tree languages - igw-gap - a - a - a - f.pdf}, doi = {10.1016/S0304-3975(02)00452-8} }