From nondeterministic Buchi and Streett automata to deterministic parity automata

被引:85
作者
Piterman, Nir [1 ]
机构
[1] Ecole Polytech Fed Lausanne, CH-1015 Lausanne, Switzerland
来源
21ST ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS | 2006年
关键词
D O I
10.1109/LICS.2006.28
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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(2n+2) states and index 2n (instead of a Rabin automaton with (12)(n)n(2n) states and n pairs). Starting from a nondeterministic Streett automaton with n states and k pairs our construction yields a deterministic parity automaton with n(n(k+2)+2) (k+ 1)(2n(k+1)) states and index 2n(k + 1) (instead of a Rabin automaton with (12)(n(k+1))n(n(k+2)) (k+ 1)(2n)(k+1) states and n(k + 1) pairs). The parity condition is much simpler than the Rabin condition. In applications such as solving games and emptiness of tree automata handling the Rabin condition involves an additional multiplier of n(2)n! (or (n(k + 1))(2) (n (k + 1))! in the case of Streett) which is saved using our construction.
引用
收藏
页码:255 / 264
页数:10
相关论文
共 35 条
[1]  
[Anonymous], 2001, Transactions on Computational Logic, DOI DOI 10.1145/377978.377993
[2]  
Björklund H, 2003, LECT NOTES COMPUT SC, V2607, P663
[3]   THEORIES OF AUTOMATA ON OMEGA-TAPES - SIMPLIFIED APPROACH [J].
CHOUEKA, Y .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 8 (02) :117-141
[4]   From verification to control: Dynamic programs for Omega-regular objectives [J].
de Alfaro, L ;
Henzinger, TA ;
Majumdar, R .
16TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 2001, :279-290
[5]   How much memory is needed to win infinite games? [J].
Dziembowski, S ;
Jurdzinski, M ;
Walukiewicz, I .
12TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 1997, :99-110
[6]  
EMERSON EA, 1988, FOCS, P328, DOI DOI 10.1109/SFCS.1988.21949
[7]  
Friedgut E, 2004, LECT NOTES COMPUT SC, V3299, P64
[8]  
Hopcroft JE., 2000, INTRO AUTOMATA THEOR
[9]  
HORN F, 2005, 2 GDV
[10]  
JUDRZINSKI M, 2006, SODA