Alternating Tree Automata and Parity Games Export

@incollection{citeulike:2946428, abstract = {Since B\"{u}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.}, author = {Kirsten, Daniel}, citeulike-article-id = {2946428}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/3-540-36387-4_9}, citeulike-linkout-1 = {http://www.springerlink.com/content/57uadeyly8tl6bab}, doi = {10.1007/3-540-36387-4_9}, journal = {Automata Logics, and Infinite Games}, keywords = {automata, copy, game-semantics}, pages = {405--411}, posted-at = {2008-07-01 03:09:51}, priority = {2}, title = {Alternating Tree Automata and Parity Games}, url = {http://dx.doi.org/10.1007/3-540-36387-4_9}, year = {2002} }

TY - CHAP ID - citeulike:2946428 L3 - citeulike-article-id:2946428 N2 - 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. JF - Automata Logics, and Infinite Games EP - 411 TI - Alternating Tree Automata and Parity Games SP - 405 KW - automata KW - copy KW - game-semantics AU - Kirsten, Daniel PY - 2002/// UR - http://dx.doi.org/10.1007/3-540-36387-4_9 ER -