Paper: From Nondeterministic Büchi and Streett Automata to Deterministic Parity Automata (at LICS 2006)

Authors: Nir Piterman

Abstract

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).

BibTeX

  @InProceedings{Piterman-FromNondeterministi,
    author = 	 {Nir Piterman},
    title = 	 {From Nondeterministic Büchi and Streett Automata to Deterministic Parity Automata},
    booktitle =  {Proceedings of the Twenty-First Annual IEEE Symposium on Logic in Computer Science (LICS 2006)},
    year =	 {2006},
    month =	 {August}, 
    pages =      {255--264},
    location =   {Seattle, Washington, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }