On complexity of verification of interacting agents' behavior
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.