21st Annual IEEE Symposium on Logic in Computer Science (LICS'06)
From Nondeterministic Buchi and Streett Automata to Deterministic Parity Automata
Seattle, Washington
August 12-August 15
ISBN: 0-7695-2631-4
In this paper we revisit Safra?s determinization constructions. We show how to construct deterministic automata with fewer states and, most importantly, parity acceptance conditions. Specifically, starting from a nondeterministic Buchi automaton with n states our construction yields a deterministic parity automaton with n^2^n+^2 states and index 2n (instead of a Rabin automaton with (12)^nn^2^n states and n pairs).