Title: "On Complexity of Multi-Agent Systems Behavior"
Abstract: `Multi-Agent System' refer to a new and generic metaphor of an artificial intelligence based computing technology. In the report we present some version of multi-agent systems based on "Heterogeneous Agent Systems" ( V.S. Subrahmanian et al.) and our results on the complexity of multi-agent systems behavior properties. The behavior properties are formulated using classical temporal logic languages and are checked relative to the transition system induced by the multi-agent system definition. Various complexity bounds of the behavior properties are established under some natural structural and semantic restrictions on agent programs and actions. Some of these bounds happen to be rather low: within deterministic or nondeterministic polynomial time.
Joint work wit Alex Dikovsky and Mars Valiev