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.
Similar content being viewed by others
References
Ågotnes, T.: 2004, ‘A Note on Syntactic Characterization of Incomplete Information in ATEL’, in Proceedings of the First Workshop on Knowledge and Games (KAG 2004), Liverpool, UK.
Alur, R., T.A. Henzinger, and O. Kupferman: 1997, ‘Alternating-time Temporal Logic’, in Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami Beach, FL, pp. 100–109.
Alur, R., T.A. Henzinger, and O. Kupferman: 1999, ‘Alternating-time Temporal Logic’, in Compositionality: The Significant Difference, Lecture Notes in Computer Science, 1536, Springer-Verlag, Berlin, pp. 23–60.
R. Alur T.A. Henzinger O. Kupferman (2002) ArticleTitle‘Alternating-time Temporal Logic’ Journal of the ACM 49 672–713 Occurrence Handle10.1145/585265.585270
Alur, R., T.A. Henzinger, F. Y. C. Mang, S. Qadeer, S. K. Rajamani, and S. Tasiran: 1998, ‘MOCHA: Modularity in Model Checking’, in Computer Aided Verification, pp. 521–525.
R. Fagin J.Y. Halpern Y. Moses M. Y. Vardi (1995) Reasoning About Knowledge The MIT Press Cambridge MA
Goranko, V. and G. van Drimmelen: 2003, ‘Decidability and Complete Axiomatization of the Alternating-time Temporal Logic’, Submitted.
J.Y. Halpern R. Fagin (1989) ArticleTitle‘Modelling Knowledge and Action in Distributed Systems’ Distributed Computing 3 IssueID4 159–177 Occurrence Handle10.1007/BF01784885
D. Harel (1984) ‘Dynamic Logic’ D. Gabbay F. Guenthner (Eds) Handbook of Philosophical Logic, Volume II: Extensions of Classical Logic D. Reidel Publishing Co. Dordrecht 497–604
J.G. Henriksen P.S. Thiagarajan (1999) ArticleTitle‘Dynamic Linear Time Temporal Logic’ Annals of Pure and Applied Logic 96 187–207 Occurrence Handle10.1016/S0168-0072(98)00039-6
G.E. Hughes M.J. Cresswell (1996) A New Introduction to Modal Logic Routledge London and New York
Jamroga, W.: 2003, ‘Some Remarks on Alternating Temporal Epistemic Logic’, in FAMAS03 – Formal Approaches to Multi-Agent Systems, Proceedings, Warsaw, Poland, pp. 133–140.
W. Jamroga W. Hoek Particlevan der (2004) ArticleTitle‘Agents that Know How to Play’ Fundamenta Informaticae 63 185–219
K. McMillan (1993) Symbolic Model Checking Kluwer Academic Publishers Norwell, MA
J.-J.C. Meyer W. Hoek Particlevan der (1995) Epistemic Logic for AI and Computer Science Cambridge University Press Cambridge UK
Moore, R.C.: 1984, ‘A Formal Theory of Knowledge and Action’, in Formal Theories of the Commonsense World, Ablex Publishing Corp, Norwood, NJ.
Morgenstern, L.: 1986, ‘A First Order Theory of Planning, Knowledge, and Action’, in J. Y. Halpern (ed.) Theoretical Aspects of Reasoning about Knowledge: Proceedings of the First Conference, Los Altos, CA, pp. 99–114, Morgan Kaufmann Publishers, Inc.
Morgenstern, L.: 1987, ‘Knowledge Preconditions for Actions and Plans’, in Proceedings of the National Conference on Artificial Intelligence. Seattle, WA, pp. 867–874. (Also published in Readings in Distributed Artificial Intelligence, Alan H. Bond and Les Gasser (eds.), pp. 151–158, Morgan Kaufmann, 1988).
van der Hoek, W., M. Roberts, and M.Wooldridge: 2004, ‘Social Laws in Alternating Time: Effectiveness, Feasibility, and Synthesis’, Technical Report ULCS-04-017, Computer Science Department, University of Liverpool.
van der Hoek, W. and M. Wooldridge: 2002, ‘Tractable Multiagent Planning for Epistemic Goals’, in Proceedings of the First International Conference on Autonomous Agents and Multiagent Systems (AAAMAS-02), Bologna, Italy.
W. Hoek Particlevan der M. Wooldridge (2003) ArticleTitle‘Cooperation, Knowledge and Time: Alternating-time Temporal Epistemic Logic and its Applications’ Studia Logica 75 125–157
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ågotnes, T. Action and Knowledge in Alternating-Time Temporal Logic. Synthese 149, 375–407 (2006). https://doi.org/10.1007/s11229-005-3875-8
Issue Date:
DOI: https://doi.org/10.1007/s11229-005-3875-8