What Agents Can Probably Enforce

• Autorzy: Bulling N. , Jamroga W.
• Języki publikacji: EN

Abstrakty

EN

Alternating-time Temporal Logic (ATL) is probably themost influential logic of strategic ability that has emerged in recent years. The idea of ATL is centered around cooperation modalities: ((A))ϒ is satisfied if the group A of agents has a collective strategy to enforce temporal property ϒ against the worst possible response from the other agents. So, the semantics of ATL shares the 'all-or-nothing' attitude of many logical approaches to computation. Such an assumption seems appropriate in some application areas (life-critical systems, security protocols, expensive ventures like space missions). In many cases, however, one might be satisfied if the goal is achieved with reasonable likelihood. In this paper, we try to soften the rigorous notion of success that underpins ATL.

Słowa kluczowe

EN

Alternating-time Temporal Logic (ATL)

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 93, nr 1-3
• Strony: 81--96
• Opis fizyczny: Bibliogr.12 poz.

Twórcy

autor

Bulling N.

autor

Jamroga W.

• Department of Informatics Clausthal University of Technology, Germany,

Bibliografia

• [1] R. Alur, T. A. Henzinger, and O. Kupferman. Alternating-time Temporal Logic. Journal of the ACM, 49:672-713, 2002.
• [2] R. Bellman. A Markovian decision process. Journal of Mathematics and Mechanics, 6:679-684, 1957.
• [3] E. Clarke and E. Emerson. Design and synthesis of synchronization skeletons using branching time temporal logic. In Proceedings of Logics of Programs Workshop, volume 131 of Lecture Notes in Computer Science, pages 52-71, 1981.
• [4] L. de Alfaro,M. Faella, T. Henzinger, R. Majumdar, and M. Stoelinga. Model checking discounted temporal properties. In Proceedings of TACAS'04, volume 2988 of LNCS, pages 57-68, 2004.
• [5] J. Gill. Computational complexity of probabilistic Turing machines. SIAM Journal on Computing, 6(4), 1977.
• [6] N. Immerman. Number of quantifiers is better than number of tape cells. Journal of Computer and System Sciences, 22(3):384-406, 1981.
• [7] W. Jamroga. A temporal logic for multi-agent MDP's. In Proceedings of the AAMAS Workshop on Formal Models and Methods for Multi-Robot Systems, pages 29-34, 2008.
• [8] J. G. Kemeny, L. J. Snell, and A. W. Knapp. Denumerable Markov Chains. Van Nostrand, 1966.
• [9] P. Y. Schobbens. Alternating-time logic with imperfect recall. Electronic Notes in Theoretical Computer Science, 85(2), 2004.
• [10] S. Toda. On the computational power of PP and P. In Proceedings of IEEE FOCS'89, pages 514-519, 1989.
• [11] L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189-201, 1979.
• [12] J. von Neumann and O. Morgenstern. Theory of Games and Economic Behaviour. Princeton University Press: Princeton, NJ, 1944.