Abstract
In this paper we settle the complexity of some basic constructions of ω-automata theory, concerning transformations of automata characterizing the set of ω-regular languages. In particular we consider Safra’s construction (for the conversion of nondeterministic Büchi automata into deterministic Rabin automata) and the appearance record constructions (for the transformation between different models of deterministic automata with various acceptance conditions). Extending results of Michel (1988) and Dziembowski, Jurdziński, and Walukiewicz (1997), we obtain sharplo wer bounds on the size of the constructed automata.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J.R. Büchi. On a decision method in restricted second order arithmetic. In Proc. International Congress on Logic, Method and Philos. Sci. 1960, pages 1–11, 1962. 97, 99
J.R. Büchi. Winning state-strategies for boolean-F σ games. manuscript, 1981. 97, 98, 103
J.R. Büchi. State-strategies for games in F σδ ∩ G δσ. Journal of Symbolic Logic, 48(4):1171–1198, December 1983. 97, 98, 103
S. Dziembowski, M. Jurdziński, and I. Walukiewicz. How much memory is needed to win infinite games? In Proc. IEEE, LICS, 1997. 97, 98, 104, 104, 104
Y. Gurevich and L. Harrington. Trees, automata and games. In Proc. 14th ACM Symp. on the Theory of Computing, pages 60–65, 1982. 97, 98, 103
S. Krishnan, A. Puri, and R. Brayton. Structural complexity of ω-automata. In 12th Annual Symposium on Theoretical Aspects of Computer Science, volume 900 of Lecture Notes in Computer Science, pages 143–156. Springer, 1995. 106, 106
L.H. Landweber. Decision problems for ω-automata. Math. System Theory, 3:376–384, 1969. 103
C. Löding. Methods for the transformation of ω-automata: Complexity and connection to second order logic. Master’s thesis, Christian-Albrechts-University of Kiel, 1998. 98
R. McNaughton. Testing and generating infinite sequences by a finite automaton. Information and Control, 9:521–530, 1966. 97
M. Michel. Complementation is much more difficult with automata on infinite words. Manuscript,CNET, Paris, 1988. 97, 97
A.W. Mostowski. Regular expressions for infinite trees and a standard form of automata. Lecture Notes in Computer Science, 208:157–168, 1984. 97, 99
D.E. Muller. Infinite sequences and finite machines. In Proc. 4th IEEE Symposium on Switching Circuit Theory and Logical design, pages 3–16, 1963. 97, 99
M.O. Rabin. Decidability of second order theories and automata on infinite trees. Transaction of the AMS, 141:1–35, 1969. 97, 99
S. Safra. On the complexity of ω-automata. In Proc. 29th IEEE Symp. on Foundations of Computer Science, pages 319–327, 1988. 97, 97, 100
S. Safra. Exponential determinization for ω-automata with strong-fairness acceptance condition. In Proc. 24th ACM Symp. on the Theory of Computing, pages 275–282, 1992. 103
S. Safra and M. Y. Vardi. On ω-automata and temporal logic. In Proc. 21th ACM Symp. on the Theory of Computing, 1989. 103
R.S. Streett. Propositional dynamic logic of looping and converse is elementary decidable. Information and Control, 54:121–141, 1982. 97, 99
W. Thomas. Languages, automata, and logic. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Language Theory, volume III, pages 385–455. Springer-Verlag, 1997. 98, 101, 102, 102, 103
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Löding, C. (1999). Optimal Bounds for Transformations of ω-Automata. In: Rangan, C.P., Raman, V., Ramanujam, R. (eds) Foundations of Software Technology and Theoretical Computer Science. FSTTCS 1999. Lecture Notes in Computer Science, vol 1738. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46691-6_8
Download citation
DOI: https://doi.org/10.1007/3-540-46691-6_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66836-7
Online ISBN: 978-3-540-46691-8
eBook Packages: Springer Book Archive