loading...
From Nondeterministic Buchi and Streett Automata to Deterministic Parity Automata
Seattle, Washington August 12-August 15
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2006.2821st Annual IEEE Symposium on Logic i ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Nir Piterman, Ecole Polytechnique F?ed?eral de Lausanne (EPFL)
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).
Citation:
Nir Piterman, "From Nondeterministic Buchi and Streett Automata to Deterministic Parity Automata," lics, pp.255-264, 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.