@article{Kurshan:Complementing:JCSS:1987,
    Abstract = {For any Buchi automaton Γ with n states which accepts the ({$\omega$}-regular) language L(Γ), an explicit construction is given for a B{\"u}chi automaton Γ with 2n states which, when Γ is deterministic, accepts exactly the complementary language L(Γ)′. It follows that the nonemptiness of complement problem for deterministic Buchi automata (i.e., whether L(Γ)′ = ⊘) is solvable in polynomial time. The best previously known construction for complementing a deterministic B{\"u}chi automaton with n states has O(24n2) states; for nondeterministic Γ, determining whether L(Γ)′ = ⊘, is known to be PSPACE-complete. Interest in deterministic B{\"u}chi automata arises from the suitability of deterministic automata in general to describe properties of physical systems; such properties have been found to be more naturally expressible by deterministic automata than by nondeterministic automata. However, if Γ is nondeterministic, then Γ provides a ``poor man's'' approximate inverse to Γ in the following sense: L(Γ)′ ⊂ L(Γ), and as nondeterministic branches of T are removed, the two languages become closer. Hence, for example, given two nondeterministic Buchi automata {$\Lambda$} and Γ, one may test for containment of their associated languages through use of the corollary that L ({$\Lambda$} ∗ Γ = ⊘ ⇒ L ({$\Lambda$}) ⊂ L(Γ) (where Γ ∗ Γ is one of the standard constructions satisfying L ({$\Lambda$} ∗ Γ) = L ({$\Lambda$}) ∩ L(Γ)). The ``error term'' L = L(Γ) ⧹ L(Γ)′ may be deter exactly, and whether L = ⊘ may be determined in time O(e2), where e is the number of edges of Γ.},
    Author = {Kurshan, R.P.},
    File = {Complementing deterministic Büchi automata in polynomial time - Kurshan (0) (0) - a - a - e.pdf},
    ISSN = {0022-0000},
    Journal = {Journal of Computer and System Sciences},
    Number = {1},
    Pages = {59--71},
    Title = {Complementing deterministic B{\"u}chi automata in polynomial time},
    URL = {http://www.sciencedirect.com/science/article/pii/0022000087900365},
    Volume = {35},
    Year = {1987},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/0022000087900365},
    bdsk-url-2 = {http://dx.doi.org/10.1016/0022-0000(87)90036-5},
    date-added = {2016-11-21 09:34:55 +0000},
    date-modified = {2016-11-21 09:35:18 +0000},
    doi = {10.1016/0022-0000(87)90036-5}
}

@article{Kurshan:Complementing:JCSS:1987, Abstract = {For any Buchi automaton Γ with n states which accepts the ({$\omega$}-regular) language L(Γ), an explicit construction is given for a B{\"u}chi automaton Γ with 2n states which, when Γ is deterministic, accepts exactly the complementary language L(Γ)′. It follows that the nonemptiness of complement problem for deterministic Buchi automata (i.e., whether L(Γ)′ = ⊘) is solvable in polynomial time. The best previously known construction for complementing a deterministic B{\"u}chi automaton with n states has O(24n2) states; for nondeterministic Γ, determining whether L(Γ)′ = ⊘, is known to be PSPACE-complete. Interest in deterministic B{\"u}chi automata arises from the suitability of deterministic automata in general to describe properties of physical systems; such properties have been found to be more naturally expressible by deterministic automata than by nondeterministic automata. However, if Γ is nondeterministic, then Γ provides a poor man's'' approximate inverse to Γ in the following sense: L(Γ)′ ⊂ L(Γ), and as nondeterministic branches of T are removed, the two languages become closer. Hence, for example, given two nondeterministic Buchi automata {$\Lambda$} and Γ, one may test for containment of their associated languages through use of the corollary that L ({$\Lambda$} ∗ Γ = ⊘ ⇒ L ({$\Lambda$}) ⊂ L(Γ) (where Γ ∗ Γ is one of the standard constructions satisfying L ({$\Lambda$} ∗ Γ) = L ({$\Lambda$}) ∩ L(Γ)). Theerror term'' L = L(Γ) ⧹ L(Γ)′ may be deter exactly, and whether L = ⊘ may be determined in time O(e2), where e is the number of edges of Γ.}, Author = {Kurshan, R.P.}, File = {Complementing deterministic Büchi automata in polynomial time - Kurshan (0) (0) - a - a - e.pdf}, ISSN = {0022-0000}, Journal = {Journal of Computer and System Sciences}, Number = {1}, Pages = {59--71}, Title = {Complementing deterministic B{\"u}chi automata in polynomial time}, URL = {http://www.sciencedirect.com/science/article/pii/0022000087900365}, Volume = {35}, Year = {1987}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/0022000087900365}, bdsk-url-2 = {http://dx.doi.org/10.1016/0022-0000(87)90036-5}, date-added = {2016-11-21 09:34:55 +0000}, date-modified = {2016-11-21 09:35:18 +0000}, doi = {10.1016/0022-0000(87)90036-5} }