From Nondeterministic Buchi and Streett Automata to Deterministic Parity Automata
Author:
Open Access
- 12 August 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10436871,p. 255-264
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 n2n+2 states and index 2n (instead of a Rabin automaton with (12)nn2n states and n pairs). Starting from a nondeterministic Streett automaton with n states and k pairs our construction yields a deterministic parity automaton with nn(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 n2n!(or(n(k+1))2(n(k+1))! in the case of Streett) which is saved using our constructionKeywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Faster Solutions of Rabin and Streett Games2006
- A deterministic subexponential algorithm for solving parity games2006
- Safraless Decision Procedures2005
- Freedom, weakness, and determinism: from linear-time to branching-time2002
- Weak alternating automata are not that weakACM Transactions on Computational Logic, 2001
- Determinization and Memoryless Winning StrategiesInformation and Computation, 1997
- Simulating alternating tree automata by nondeterministic automata: New results and new proofs of the theorems of Rabin, McNaughton and SafraTheoretical Computer Science, 1995
- Automata on Infinite Objects1990
- On the synthesis of a reactive module1989
- Testing and generating infinite sequences by a finite automatonInformation and Control, 1966