×

A fully abstract model for the exchange of information in multi-agent systems. (English) Zbl 1038.68019

Summary: We present a semantic theory for the exchange of information in multi-agent systems. We consider the multi-agent programming language agent communication programming language, which integrates the paradigms of concurrent constraint programming and Communicating Sequential Processes (CSP). The constraint programming techniques are used to represent and process information, whereas the synchronous communication mechanism from CSP is generalised to enable the exchange of information. The semantics of the language, which is based on a generalisation of traditional failure semantics, is shown to be fully abstract with respect to observing of each terminating computation its final global store of information.

MSC:

68N15 Theory of programming languages
68Q55 Semantics in the theory of computing

Software:

KQML
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Austin, J. L., How to do Things with Words (1962), Oxford University Press: Oxford University Press Oxford
[2] Bergstra, J. A.; Klop, J. W., Process algebra for synchronous communication, Inform. and Control, 60, 109-137 (1984) · Zbl 0597.68027
[3] Bergstra, J. A.; Klop, J. W.; Olderog, E.-R., Readies and failures in the algebra of communicating processes, SIAM J. Comput., 17, 1134-1177 (1988) · Zbl 0677.68089
[4] Brim, L.; Gilbert, D.; Jacquet, J.-M.; Křetı́nský, M., A process algebra for synchronous concurrent constraint programming, (Hanus, M.; Rodriquez-Artalejo, M., Proc. 5th Conf. Algebraic and Logic Programming, Lecture Notes in Computer Science, Vol. 1139 (1996), Springer: Springer Berlin), 165-178
[5] Brookes, S. D.; Hoare, C. A.R.; Roscoe, W., A theory of communicating sequential processes, J. ACM, 31, 499-560 (1984) · Zbl 0628.68025
[6] de Boer, F. S.; Palamidessi, C., A fully abstract model for concurrent constraint programming, (Proc. Fourth Internat. Joint Conf. Theory and Practice of Software Development (TAPSOFT), Lecture Notes in Computer Science, Vol. 493 (1991), Springer: Springer Berlin), 296-319 · Zbl 0967.68516
[7] de Boer, F. S.; van Eijk, R. M.; van derHoek, W.; Meyer, J.-J. Ch., Failure semantics for the exchange of information in multi-agent systems, (Palamidessi, C., Proc. 11th Internat. Conf. Concurrency Theory (CONCUR 2000), Lecture Notes in Computer Science, Vol. 1877 (2000), Springer: Springer Heidelberg), 214-228 · Zbl 0999.68210
[8] Finin, T.; McKay, D.; Fritzson, R.; McEntire, R., KQML: An information and knowledge exchange protocol, (Fuchi, K.; Yokoi, ., Knowledge Building and Knowledge Sharing (1994), Ohmsha and IOS Press: Ohmsha and IOS Press Amsterdam)
[9] Halpern, J. Y.; Moses, Y., A guide to the completeness and complexity for modal logics of knowledge and belief, Artificial Intelligence, 54, 319-379 (1992) · Zbl 0762.68029
[10] Henkin, L.; Monk, J. D.; Tarski, A., Cylindric Algebras (Part I) (1971), North-Holland: North-Holland Amsterdam · Zbl 0214.01302
[11] Hoare, C. A.R., Communicating sequential processes, Commun. ACM, 21, 8, 666-677 (1978) · Zbl 0383.68028
[12] Pitt, J.; Mamdani, A., Some remarks on the semantics of FIPA’s agent communication language, Autonomous Agents and Multi-Agent Systems, 2, 4, 333-356 (1999)
[13] Reiter, R., On closed world data bases, (Gaillaire, H.; Minker, J., Logic and Data Bases (1978), Plenum Press: Plenum Press New York), 55-76
[14] Réty, J.-H., Distributed concurrent constraint programming, Fund. Inform., 34, 3, 323-346 (1998) · Zbl 0943.68025
[15] V.A. Saraswat, M. Rinard. Concurrent constraint programming, in: Proc. 17th ACM Symp. Principles of Programming Languages (POPL’90), 1990, pp. 232-245.; V.A. Saraswat, M. Rinard. Concurrent constraint programming, in: Proc. 17th ACM Symp. Principles of Programming Languages (POPL’90), 1990, pp. 232-245.
[16] V.A. Saraswat, M. Rinard, P. Panangaden, Semantic foundations of concurrent constraint programming, in: Proc. 18th ACM Symp. Principles of Programming Languages (POPL’91), 1991, pp. 333-352.; V.A. Saraswat, M. Rinard, P. Panangaden, Semantic foundations of concurrent constraint programming, in: Proc. 18th ACM Symp. Principles of Programming Languages (POPL’91), 1991, pp. 333-352.
[17] Searle, J. R., Speech Acts: An Essay in the Philosophy of Language (1969), Cambridge University Press: Cambridge University Press Cambridge
[18] van Breughel, F., Failures, finiteness and full abstraction, (Brookes, S.; Mislove, M., Proc. Thirteenth Conf. Mathematical Foundations of Programming Semantics. Proc. Thirteenth Conf. Mathematical Foundations of Programming Semantics, Electronic Notes in Theoretical Computer Science, Vol. 6 (1997), Elsevier: Elsevier New York) · Zbl 0911.68117
[19] van Eijk, R. M.; de Boer, F. S.; van derHoek, W.; Meyer, J.-J. Ch., Systems of communicating agents, (Prade, Henri, Proc. 13th Biennial European Conf. Artificial Intelligence (ECAI’98) (1998), Wiley: Wiley Chichester, United Kingdom), 293-297
[20] R.M. van Eijk, F.S. de Boer, W. van derHoek, J.-J.Ch. Meyer, Information-passing and belief revision in multi-agent systems, in: J.P.M. M üller, M.P. Singh, A.S. Rao (Eds.), Intelligent Agents V, Proc. 5th Internat. Workshop on Agent Theories, Architectures, and Languages (ATAL’98), Lecture Notes in Artificial Intelligence, Vol. 1555, Springer, Heidelberg, 1999.; R.M. van Eijk, F.S. de Boer, W. van derHoek, J.-J.Ch. Meyer, Information-passing and belief revision in multi-agent systems, in: J.P.M. M üller, M.P. Singh, A.S. Rao (Eds.), Intelligent Agents V, Proc. 5th Internat. Workshop on Agent Theories, Architectures, and Languages (ATAL’98), Lecture Notes in Artificial Intelligence, Vol. 1555, Springer, Heidelberg, 1999.
[21] van Eijk, R. M.; de Boer, F. S.; van derHoek, W.; Meyer, J.-J. Ch., Open multi-agent systems: Agent communication and integration, (Jennings, N. R.; Lespèrance, Y., Intelligent Agents VI, Proc. 6th Internat. Workshop on Agent Theories, Architectures, and Languages (ATAL’99), Lecture Notes in Artificial Intelligence, Vol. 1757 (2000), Springer: Springer Heidelberg), 218-232 · Zbl 0970.68662
[22] van Eijk, R. M.; de Boer, F. S.; van derHoek, W.; Meyer, J.-J. Ch., On dynamically generated ontology translators in agent communication, Internat. J. Intell. Systems, 16, 5, 587-607 (2001) · Zbl 0979.68013
[23] Wooldridge, M., Verifiable semantics for agent communication languages, (Proc. 3rd Internat. Conf. Multi-Agent Systems (ICMAS’98) (1998), IEEE Computer Society: IEEE Computer Society Los Alamitos, California), 349-356
[24] Wooldridge, M.; Jennings, N., Intelligent agentstheory and practice, The Knowledge Eng. Rev., 10, 2, 115-152 (1995)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.