On complexity of verification of interacting agents' behavior

, &
Annals of Pure and Applied Logic 141 (3):336-362 (2006)
  Copy   BIBTEX

Abstract

This paper studies the complexity of behavior of multi-agent systems. Behavior properties are formulated using classical temporal logic languages and are checked with respect to the transition system induced by the definition of the multi-agent system. We establish various tight complexity bounds of the behavior properties under natural structural and semantic restrictions on agent programs and actions

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2005.12.003

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,139

External links

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

Through your library

My notes

Similar books and articles

Compositional verification of multi-agent systems in temporal multi-epistemic logic.Joeri Engelfriet, Catholijn M. Jonker & Jan Treur - 2002 - Journal of Logic, Language and Information 11 (2):195-225.
Formal Modelling and Verification of Probabilistic Resource Bounded Agents.Hoang Nga Nguyen & Abdur Rakib - 2023 - Journal of Logic, Language and Information 32 (5):829-859.
AgentTime: A Distributed Multi-agent Software System for University's Timetabling.Eduard Babkin, Habib Abdulrab & Tatiana Babkina - 2009 - In Moulay Aziz-Alaoui & Cyrille Bertelle (eds.), From System Complexity to Emergent Properties. Springer. pp. 341--354.
A formalism for multi-level emergent behaviours in designed component-based systems and agent-based simulations.Chih-Chun Chen, Sylvia B. Nagl & Christopher D. Clack - 2009 - In Moulay Aziz-Alaoui & Cyrille Bertelle (eds.), From System Complexity to Emergent Properties. Springer. pp. 101--114.
Enabling the Analysis of Emergent Behavior in Future Electrical Distribution Systems Using Agent-Based Modeling and Simulation.Sonja Kolen, Stefan Dähling, Timo Isermann & Antonello Monti - 2018 - Complexity 2018:1-16.
Multi-agent Justification Logic: communication and evidence elimination. [REVIEW]Bryan Renne - 2012 - Synthese 185 (S1):43-82.
The ontological properties of social roles in multi-agent systems: Definitional dependence, powers and roles playing roles. [REVIEW]Guido Boella & Leendert van der Torre - 2007 - Artificial Intelligence and Law 15 (3):201-221.
A Reasoning Method based on Spatio-Temporal.Seyed Ahmad Mirsanei - 2016 - International Journal of Computer and Information Technologies (Ijocit) 4 (1): 27-32..
Complexity of logics for multi-agent systems with restricted modal context.M. Dziubinski - 2013 - Logic Journal of the IGPL 21 (3):355-379.
Unification and Finite Model Property for Linear Step-Like Temporal Multi-Agent Logic with the Universal Modality.Stepan I. Bashmakov & Tatyana Yu Zvereva - 2022 - Bulletin of the Section of Logic 51 (3):345-361.

Analytics

Added to PP
2013-12-31

Downloads
31 (#730,306)

6 months
9 (#492,507)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Biography of Alexandre Dikovsky.Denis Béchet & Michael Dekhtyar - 2017 - Journal of Logic, Language and Information 26 (4):333-340.

Add more citations

References found in this work

Agent-oriented programming.Yoav Shoham - 1993 - Artificial Intelligence 60 (1):51-92.

Add more references