Abstract
The complexity of multi-agent systems behavior properties is studied. The behavior properties are formulated using first order temporal logic languages and are checked relative to the state transition diagram induced by the multi-agent system. Various tight complexity bounds of the behavior properties are established under natural structural and semantic restrictions on agent programs and actions. There are some interesting cases, where the check problem is decidable in deterministic or nondeterministic polynomial time.
This work was sponsored by the Russian Fundamental Studies Foundation (Grants 01-01-00278, 00-01-00254 and 02-01-00652).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Apt, K. R., Logic Programming. In: J. van Leeuwen (Ed.) Handbook of Theoretical Computer Science. Volume B. Formal Models and Semantics, Chapter 10, Elsevier Science Publishers B.V. 1990, 493–574.
Bylander, T., The computational Complexity of Propositional STRIPS Planning, Artificial Intelligence, 69:165–204, 1994.
Clarke, E. M., Emerson, E. A. Design and synthesis of synchronization skeletons using branching time temporal logic. In: Proc.of Workshop on Logics of Programs, Lecture Notes in Computer Science, N. 181, 1981, 52–71.
Calvanese, D., De Giacomo, G., and Vardi, M.Y., Reasoning about actions and planning in LTL action theories, Proc. of the 8th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR’02), 593–602, 2002.
Clarke, E. M., Grumberg, O. and Peled, D., Model Checking, MIT Press, 2000.
Dekhtyar, M., Dikovsky, A., On Homeostatic Behavior of Dynamic Deductive Data Bases. In: Proc. 2nd Int. A.P.Ershov Memorial Conference “Perspective ofSystems Informatics”, Lect. Notes in CS, N. 1181, 1996, 420–432.
Dekhtyar, M., Dikovsky, A., and Valiev, M., Applying temporal logic to analysis of behavior of cooperating logic programs. Lect. Notes in CS, N. 1755, 2000, 228–234.
Eiter, T., Fink, M., Sabbatini, G., and Tompits, H., “Reasoning about Evolving Nonmonotonic Knowledge Bases”, Proc. of LPAR01, 2001.
Emerson, E. A. Temporal and modal logic. In: J. van Leeuwen (Ed.), "Handbook of Theor. Comput. Sci.", Elsevier Sci. Publishers, 1990.
Emerson, E. A. Model checking and the mu-calculus. In: N. Immerman, P. H. Kolaitis (Eds.), “Descriptive Complexity and Finite Models”. Proc. of a DIMACS Workshop, 1996, 185–214.
Erol, K., Nau, D.S., and Subrahmanian, V.S., Complexity, Decidability and Undecidability Results for Domain-Independent Planning, Artificial Intelligence Journal, 76(1–2):75–88, 1995.
Fagin, R., Halpern, J.Y., Moses, Y. and Vardi, M., Reasoning about Knowledge, 1995, MIT Press.
Fisher, M., Wooldridge, M., Specifying and Verifying Distributed Intelligent Systems. In: M. Filgueiras and L. Damas (Eds.) Progress in Artificial Intelligence-Sixth Portuguese Conf. on Artificial Intelligence. LNAI, N. 727, 1993, pp. 13–28, Springer-Verlag: Berlin, Germany.
Jennings, N., Sycara, K. and Wooldridge, M. A roadmap of agent research and development Autonomous Agents and Multi-Agent Systems, 1998, 1(1):7–38.
Müller, J. P., Architectures and applications of intelligent agents: A survey. The Knowledge Engineering Review, 1998, 13(4):353–380.
Kozen, D., Results on the Propositional μ-calculus. Theoretical Computer Science, 1983, v. 27, pp. 333–354.
Petrie, C., What is an agent? In: J.P. Müller, M. J. Wooldridge, and N. R. Jennings (Eds.) Intelligent Agents III-Proc. of the Third Intern. Workshop on Agent Theories, Architectures, and Languages, Lecture Notes in Artificial Intelligence, N. 1193, 41–43. Springer-Verlag.
Reiter, R. Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems. MIT Press, 2001.
Sistla, A. P., Clarke, E. M., The complexity of propositional linear temporal logic. J.ACM, 32(3), 1985, 733–749.
Subrahmanian, V. S., Bonatti, P., Dix, J., et al., Heterogeneous Agent Systems, MIT Press, 2000.
Vardi, M., Wolper, P., An automata-theoretic approach to automatic program verification. In: Proc. of the IEEE Symposium on Logic in Computer Science, 1986, 332–344.
Wooldridge, M., The Computational Complexity of Agent Design Problem. In: E. Durfee, (Ed.) Proc. of the Fourth Intern. Conf. on Multi-Agent Systems (ICMAS 2000), IEEE Press, 2000.
Wooldridge, M., Jennings N. Intelligent agents: Theory and practice. The Knowledge Engineering Review, 1995, 10(2).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dekhtyar, M., Dikovsky, A., Valiev, M. (2002). Complexity of Multi-agent Systems Behavior. In: Flesca, S., Greco, S., Ianni, G., Leone, N. (eds) Logics in Artificial Intelligence. JELIA 2002. Lecture Notes in Computer Science(), vol 2424. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45757-7_11
Download citation
DOI: https://doi.org/10.1007/3-540-45757-7_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44190-8
Online ISBN: 978-3-540-45757-2
eBook Packages: Springer Book Archive