From Nondeterministic Büchi and Streett Automata to Deterministic Parity Automata
Author:
- Nir PitermanNPNir Piterman
Preprint
Abstract
In this paper we revisit Safra's determinization constructions for automata on infinite words. We show how to construct deterministic automata with fewer states and, most importantly, parity acceptance conditions. Determinization is used in numerous applications, such as reasoning about tree automata, satisfiability of CTL*, and realizability and synthesis of logical specifications. The upper bounds for all these applications are reduced by using the smaller deterministic automata produced by our construction. In addition, the parity acceptance conditions allows to use more efficient algorithms (when compared to handling Rabin or Streett acceptance conditions).Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Weak alternating automata are not that weak2002
- Introduction to automata theory, languages, and computation, 2nd editionACM SIGACT News, 2001
- Computing the Rabin Index of a Parity AutomatonRAIRO - Theoretical Informatics and Applications, 1999
- 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
- Theories of automata on ω-tapes: A simplified approachJournal of Computer and System Sciences, 1974
- Automata on Infinite Objects and Church’s Problem1972
- Testing and generating infinite sequences by a finite automatonInformation and Control, 1966
- Finite Automata and Their Decision ProblemsIBM Journal of Research and Development, 1959