@inproceedings{10.1007/3-540-45315-6_18,
    Abstract = {Different types of nondeterministic automata on infinite words differ in their succinctness and in the complexity for their nonemptiness problem. A simple translation of a parity automaton to an equivalent B{\"u}chi automaton is quadratic: a parity automaton with n states, m transitions, and index k may result in a B{\"u}chi automaton of size O((n + m)k). The best known algorithm for the nonemptiness problem of parity automata goes through B{\"u}chi automata, leading to a complexity of O((n + m)k). In this paper we show that while the translation of parity automata to B{\"u}chi automata cannot be improved, the special structure of the acceptance condition of parity automata can be used in order to solve the nonemptiness problem directly, with a dynamic graph algorithm of complexity O((n + m) log k).},
    Address = {Berlin, Heidelberg},
    Author = {King, Valerie and Kupferman, Orna and Vardi, Moshe Y.},
    BookTitle = {Foundations of Software Science and Computation Structures},
    Editor = {Honsell, Furio and Miculan, Marino},
    File = {OnePlayerParity (0) - a - a - a.pdf},
    ISBN = {978-3-540-45315-4},
    Pages = {276--286},
    Publisher = {Springer Berlin Heidelberg},
    Title = {On the Complexity of Parity Word Automata},
    Year = {2001},
    date-added = {2018-03-21 18:44:37 +0000},
    date-modified = {2018-03-21 18:44:37 +0000},
    doi = {10.1007/3-540-45315-6_18}
}

@inproceedings{10.1007/3-540-45315-6_18, Abstract = {Different types of nondeterministic automata on infinite words differ in their succinctness and in the complexity for their nonemptiness problem. A simple translation of a parity automaton to an equivalent B{\"u}chi automaton is quadratic: a parity automaton with n states, m transitions, and index k may result in a B{\"u}chi automaton of size O((n + m)k). The best known algorithm for the nonemptiness problem of parity automata goes through B{\"u}chi automata, leading to a complexity of O((n + m)k). In this paper we show that while the translation of parity automata to B{\"u}chi automata cannot be improved, the special structure of the acceptance condition of parity automata can be used in order to solve the nonemptiness problem directly, with a dynamic graph algorithm of complexity O((n + m) log k).}, Address = {Berlin, Heidelberg}, Author = {King, Valerie and Kupferman, Orna and Vardi, Moshe Y.}, BookTitle = {Foundations of Software Science and Computation Structures}, Editor = {Honsell, Furio and Miculan, Marino}, File = {OnePlayerParity (0) - a - a - a.pdf}, ISBN = {978-3-540-45315-4}, Pages = {276--286}, Publisher = {Springer Berlin Heidelberg}, Title = {On the Complexity of Parity Word Automata}, Year = {2001}, date-added = {2018-03-21 18:44:37 +0000}, date-modified = {2018-03-21 18:44:37 +0000}, doi = {10.1007/3-540-45315-6_18} }