Knowledge-Based Asynchronous Programming

• Autorzy: de Haan H. W. , Hesselink W. H. , Renardel de Lavalette G. R.
• Języki publikacji: EN

Abstrakty

EN

A knowledge-based program is a high-level description of the behaviour of agents in terms of knowledge that an agent must have before (s)he may perform an action. The definition of the semantics of knowledge-based programs is problematic, since it involves a vicious circle; the knowledge of an agent is defined in terms of the possible behaviours of the program, while the possible behaviours are determined by the actions which depend on knowledge. We define the semantics of knowledge-based programs via an iteration approach generalizing the well-known fixpoint construction. We propose a specific iteration as the semantics of a knowledge-based program, and justify our choice by a number of examples, including the Unexpected Hanging Paradox.

Słowa kluczowe

EN

knowledge based programming; semantics of programming languages; concurrent programming; asynchronicity; unexpected hanging paradox

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 63, nr 2,3
• Strony: 259--281
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

de Haan H. W.

• Institute for Mathematics and Computing Science, University of Groningen, P.O. Box 800, 9700 AV Groningen, The Netherlands

autor

Hesselink W. H.

• Institute for Mathematics and Computing Science, University of Groningen, P.O. Box 800, 9700 AV Groningen, The Netherlands

autor

Renardel de Lavalette G. R.

• Institute for Mathematics and Computing Science, University of Groningen, P.O. Box 800, 9700 AV Groningen, The Netherlands

Bibliografia

• [1] M. Abadi and L. Lamport, The existence of refinement mappings, Theoretical Computer Science 82, 1991, pp. 253-284.
• [2] K.R. Apt and E.-R. Olderog, Verification of Sequential and Concurrent Programs, Springer Verlag, 1991.
• [3] J.W. de Bakker, Mathematical Theory of Program Correctness, Prentice-Hall, 1980.
• [4] A. Baltag, A logic for suspicious players: epistemic actions and belief updates in games, Bulletin of Economic Research 54 (1), 2002, pp. 1-45.
• [5] K.M. Chandy and J. Misra, How processes learn, Distributed Computing 1 (1), 1986, pp. 40-52.
• [6] H.P. van Ditmarsch, Descriptions of game actions, Journal of Logic, Language and Information (JoLLI), volume 11, 2002, pp. 349-365.
• [7] K. Engelhardt, R. van der Meyden and Y. Moses, A refinement theory that supports reasoning about knowledge and time for synchronous agents, 8th International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR 2001), vol. 2250 of LNAI, Springer-Verlag, Dec 2002, pp. 125-141.
• [8] R. Fagin, J.Y. Halpern, Y. Moses, and M.Y. Vardi, Reasoning about Knowledge, MIT Press, 1995.
• [9] R. Fagin, J.Y. Halpern, Y. Moses, and M.Y. Vardi, Knowledge-based programs, Distributed Computing 10 (4), 1997, pp. 199-225.
• [10] J. Gerbrandy, Bisimulations on Planet Kripke, ILLC Dissertation Series, Amsterdam, 1999.
• [11] H.W. de Haan, W.H. Hesselink, G.R. Renardel de Lavalette, Knowledge-based programming inspired by an asynchronous hardware leader election problem In: B. Dunin-Kęplicz, R. Verbrugge (eds.): FAMAS’03, ETAPS 2003,Warsaw, Poland. pp. 117-132.
• [12] J.Y. Halpern and L.D. Zuck, A little knowledge goes a long way: knowledge-based derivations and correctness proofs for a family of protocols, Journal of the ACM 39 (3), 1992, pp. 449-478.
• [13] D. Harel, D. Kozen and J. Tiuryn, Dynamic Logic, MIT Press, 2000.
• [14] W.H. Hesselink, Programs, Recursion and Unbounded Choice, Predicate Transformation Semantics and Transformation Rules, Cambridge University Press, 1992, (Cambridge Tracts in Theoretical Computer Science 27).
• [15] W.H. Hesselink, Eternity variables to simulate specifications, In: E.A. Boiten, B. Möller (eds.): Proceedings Mathematics of Program Construction, Dagstuhl, 2002 (LNCS 2386), pp. 117-130.
• [16] D.J. O’Connor, Pragmatic paradoxes, Mind 57, 1948, pp. 358-359.
• [17] S. Katz and G. Taubenfeld, What processes know: definitions and proof methods, Proceedings of the 5th ACM Symposium on Principles of Distributed Computing, 1986, pp. 249-262.
• [18] R. van der Meyden, Common knowledge and update in finite environments, Information and Computation 140 (2), 1998, pp. 115-157.
• [19] Y. Moses and O. Kislev, Knowledge-oriented programming (extended abstract), Proceedings of the 10th ACM Symposium on Principles of Distributed Computing, 1993, pp. 261-270.
• [20] B. Sanders, A predicate transformer approach to knowledge and knowledge-based protocols, Proceedings of the 10th ACM Symposium on Principles of Distributed Computing, 1991, pp. 217-230.
• [21] F. Stulp and R. Verbrugge, A knowledge-based algorithm for the Internet protocol TCP, Bulletin of Economic Research 54 (1), 2002, pp. 69-94.
• [22] M.Y. Vardi, Implementing knowledge-based programs, Proceedings of the 6th Conference on Theoretical Aspects of Rationality and Knowledge (TARK), 1996, pp. 15-30.
• [23] G. Winskel, The Formal Semantics of Programming Languages: an Introduction, The MIT Press, 1993.