Alternating-time temporal logic
Alur R, Henzinger TA, Kupferman O. 1997. Alternating-time temporal logic. Proceedings of the 38th Annual Symposium on Foundations of Computer Science. FOCS: Foundations of Computer Science, 100–109.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Alur, Rajeev;
Henzinger, Thomas AISTA 
;
Kupferman, Orna
;
Kupferman, OrnaAbstract
Temporal logic comes in two varieties: linear-time temporal logic assumes implicit universal quantification over all paths that are generated by system moves; branching-time temporal logic allows explicit existential and universal quantification over all paths. We introduce a third, more general variety of temporal logic: alternating-time temporal logic offers selective quantification over those paths that are possible outcomes of games, such as the game in which the system and the environment alternate moves. While linear-time and branching-time logics are natural specification languages for closed systems, alternating-time logics are natural specification languages for open systems. For example, by preceding the temporal operator “eventually” with a selective path quantifier, we can specify that in the game between the system and the environment, the system has a strategy to reach a certain state. Also the problems of receptiveness, realizability, and controllability can be formulated as model-checking problems for alternating-time formulas
Publishing Year
Date Published
1997-01-01
Proceedings Title
Proceedings of the 38th Annual Symposium on Foundations of Computer Science
Acknowledgement
We thank Luca de Alfaro, Kousha Etessami, Salvatore La Torre, P. Madhusudan, Amir Pnueli, Moshe Vardi, Thomas Wilke, and Mihalis Yannakakis for helpful discussions. We also thank Freddy Mang for comments on a draft of this manuscript.
Page
100 - 109
Conference
FOCS: Foundations of Computer Science
Conference Location
Washington, DC, United States
Conference Date
1997-10-19 – 1997-10-22
ISSN
IST-REx-ID
Cite this
Alur R, Henzinger TA, Kupferman O. Alternating-time temporal logic. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science. Association for Computing Machinery (ACM); 1997:100-109. doi:10.1145/585265.585270
Alur, R., Henzinger, T. A., & Kupferman, O. (1997). Alternating-time temporal logic. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science (pp. 100–109). Washington, DC, United States: Association for Computing Machinery (ACM). https://doi.org/10.1145/585265.585270
Alur, Rajeev, Thomas A Henzinger, and Orna Kupferman. “Alternating-Time Temporal Logic.” In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 100–109. Association for Computing Machinery (ACM), 1997. https://doi.org/10.1145/585265.585270.
R. Alur, T. A. Henzinger, and O. Kupferman, “Alternating-time temporal logic,” in Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Washington, DC, United States, 1997, pp. 100–109.
Alur R, Henzinger TA, Kupferman O. 1997. Alternating-time temporal logic. Proceedings of the 38th Annual Symposium on Foundations of Computer Science. FOCS: Foundations of Computer Science, 100–109.
Alur, Rajeev, et al. “Alternating-Time Temporal Logic.” Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Association for Computing Machinery (ACM), 1997, pp. 100–09, doi:10.1145/585265.585270.
Google Scholar