On the complexity of omega -automata
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 319-327
- https://doi.org/10.1109/sfcs.1988.21948
Abstract
Automata on infinite words were introduced by J.R. Buchi (1962) in order to give a decision procedure for S1S, the monadic second-order theory of one successor. D.E. Muller (1963) suggested deterministic omega -automata as a means of describing the behavior of nonstabilising circuits. R. McNaughton (1966) proved that classes of languages accepted by nondeterministic Buchi automata and by deterministic Muller automata are the same. His construction and its proof are quite complicated, and the blow-up of the construction is double exponential. The author presents a determinisation construction that is simpler and yields a single exponent upper bound for the general case. This construction is essentially optimal. It can also be used to obtain an improved complementation construction for Buchi automata that is also optimal. Both constructions can be used to improve the complexity of decision procedures that use automata-theoretic techniques.<>Keywords
This publication has 18 references indexed in Scilit:
- On the complementation of Büchi automataTheoretical Computer Science, 1986
- Propositional dynamic logic of looping and converse is elementarily decidableInformation and Control, 1982
- Theories of automata on ω-tapes: A simplified approachJournal of Computer and System Sciences, 1974
- The monadic second order theory of ω1Published by Springer Nature ,1973
- Automata on Infinite Objects and Church’s ProblemCBMS Regional Conference Series in Mathematics, 1972
- Büchi’s Monadic Second Order Successor ArithmeticLecture Notes in Mathematics, 1970
- Decidability of Second-Order Theories and Automata on Infinite TreesTransactions of the American Mathematical Society, 1969
- Testing and generating infinite sequences by a finite automatonInformation and Control, 1966
- Infinite sequences and finite machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1963
- Finite Automata and Their Decision ProblemsIBM Journal of Research and Development, 1959