Abstract
Since Büchi’s work in 1960 [17], automata play an important role in logic. Numerous different notions of automata provide decision and complexity results in various kinds of logic. Often, one develops a method to translate some given formula ϕ into an appropriate finite automaton A such that L(ϕ) = L(A). Such a translation reduces the model checking problem and the satisfiability problem in some logic to the word problem and the emptiness problem for finite automata. Moreover, such a translation provides algorithms to solve the model checking and the satisfiability problems on a computer. Consequently, one is interested in the decidability and the complexity of the word and emptiness problems of automata.
This is a preview of subscription content, log in via an institution to check access.
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
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Kirsten, D. (2002). Alternating Tree Automata and Parity Games. In: Grädel, E., Thomas, W., Wilke, T. (eds) Automata Logics, and Infinite Games. Lecture Notes in Computer Science, vol 2500. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36387-4_9
Download citation
DOI: https://doi.org/10.1007/3-540-36387-4_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00388-5
Online ISBN: 978-3-540-36387-3
eBook Packages: Springer Book Archive