Alternation

Abstract Alternation was introduced in the late 1970s as a complexitytheoretic construct, capturing the computational aspect of games. Since then it has also been shown that alternation can be viewed as a powerful high level algorithmic construct, which is particularly suitable for automated reasoning. In this talk I will explain how to turn alternation from a complexity-theoretic construct to an algorithmic construct and demonstrate its applicability in the context of modal and temporal reasoning. A particular emphasis will be put on the use of alternating automata as an algorithmic tool.

Authors

• Moshe Y. Vardi

Keywords

No keywords are indexed for this paper.