Action and Knowledge in Alternating-Time Temporal Logic

Synthese 149 (2):375-407 (2006)
  Copy   BIBTEX

Abstract

Alternating-time temporal logic (ATL) is a branching time temporal logic in which statements about what coalitions of agents can achieve by strategic cooperation can be expressed. Alternating-time temporal epistemic logic (ATEL) extends ATL by adding knowledge modalities, with the usual possible worlds interpretation. This paper investigates how properties of agents’ actions can be expressed in ATL in general, and how properties of the interaction between action and knowledge can be expressed in ATEL in particular. One commonly discussed property is that an agent should know about all available actions, i.e., that the same actions should be available in indiscernible states. Van der Hoek and Wooldridge suggest a syntactic expression of this semantic property. This paper shows that this correspondence in fact does not hold. Furthermore, it is shown that the semantic property is not expressible in ATEL at all. In order to be able to express common and interesting properties of action in general and of the interaction between action and knowledge in particular, a generalization of the coalition modalities of ATL is proposed. The resulting logics, ATL-A and ATEL-A, have increased expressiveness without loosing ATL’s and ATEL’s tractability of model checking.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,593

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Alternating automata and temporal logic normal forms.Clare Dixon, Alexander Bolotov & Michael Fisher - 2005 - Annals of Pure and Applied Logic 135 (1-3):263-285.
A logic of strategic ability under bounded memory.Thomas Ågotnes & Dirk Walther - 2009 - Journal of Logic, Language and Information 18 (1):55-77.
Branching-time logics repeatedly referring to states.Volker Weber - 2009 - Journal of Logic, Language and Information 18 (4):593-624.
Adding a temporal dimension to a logic system.Marcelo Finger & Dov M. Gabbay - 1992 - Journal of Logic, Language and Information 1 (3):203-233.
The complexity of temporal logic over the reals.Mark Reynolds - 2010 - Annals of Pure and Applied Logic 161 (8):1063-1096.

Analytics

Added to PP
2009-01-28

Downloads
124 (#135,233)

6 months
4 (#319,344)

Historical graph of downloads
How can I increase my downloads?

References found in this work

A New Introduction to Modal Logic.M. J. Cresswell & G. E. Hughes - 1996 - New York: Routledge. Edited by M. J. Cresswell.
Dynamic Logic.Lenore D. Zuck & David Harel - 1989 - Journal of Symbolic Logic 54 (4):1480.
A New Introduction to Modal Logic.G. E. Hughes & M. J. Cresswell - 1996 - Studia Logica 62 (3):439-441.
A New Introduction to Modal Logic.G. E. Hughes - 1996 - New York: Psychology Press. Edited by M. J. Cresswell.

View all 12 references / Add more references