Article

Free access

Algorithmic knowledge

Authors:

Joseph Y. Halpern,

Moshe Y. VardiAuthors Info & Claims

TARK '94: Proceedings of the 5th conference on Theoretical aspects of reasoning about knowledge

Pages 255 - 266

Published: 13 March 1994 Publication History

Abstract

The standard model of knowledge in multi-agent systems suffers from what has been called the <i>logical omniscience problem:</i> agents know all tautologies, and know all the logical consequences of their knowledge. For many types of analysis, this turns out not to be a problem. Knowledge is viewed as being <i>ascribed</i> by the system designer to the agents; agents are not assumed to compute their knowledge in any way, nor is it assumed that they can necessarily answer questions based on their knowledge. Nevertheless, in many applications that we are interested in, agents need to <i>act</i> on their knowledge. In such applications, an externally ascribed notion of knowledge is insufficient: clearly an agent can base his actions only on what he <i>explicitly</i> knows. Furthermore, an agent that has to act on his knowledge has to be able to compute this knowledge; we do need to take into account the algorithms available to the agent, as well as the "effort" required to compute knowledge. In this paper, we show how the standard model can be modified in a natural way to take the computational aspects of knowledge into account.

References

[1]

{BGP89} P. Berman, J. Garay, and K. J. Perry. Towards optimal distributed consensus. In Proc. 30th IEEE Symp. on Foundations of Computer Science, pages 410--415, 1989.

Digital Library

[2]

{Bin90} K. Binmore. Essays on the Foundations of Game Theory. Basil Blackwell, Oxford, UK, 1990.

[3]

{CM86} K. M. Chandy and J. Misra. How processes learn. Distributed Computing, 1(1):40--52, 1986.

Digital Library

[4]

{Elg91} J. J. Elgot-Drapkin. Step-logic and the three-wise-men problem. In Proc. National Conference on Artificial Intelligence (AAAI '91), 1991.

[5]

{EP90} J. J. Elgot-Drapkin and D. Perlis. Reasoning situation in time I: Basic concepts. Journal of Experimental and Theoretical Artificial Intelligence, 2(1):75--98, 1990.

Digital Library

[6]

{FH88} R. Fagin and J. Y. Halpern. Belief, awareness, and limited reasoning. Artificial Intelligence, 34:39--76, 1988.

Digital Library

[7]

{FHMV94} R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi. Reasoning about Knowledge. MIT Press, Cambridge, MA, To appear, 1994.

[8]

{GMR89} S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186--208, February 1989.

Digital Library

[9]

{Hal87} J. Y. Halpern. Using reasoning about knowledge to analyze distributed systems. In J. F. Traub, B. J. Grosz, B. W. Lampson, and N. J. Nilsson, editors, Annual Review of Computer Science, Vol. 2, pages 37--68. Annual Reviews Inc., Palo Alto, CA, 1987.

[10]

{Hal93} J. Y. Halpern. Reasoning about knowledge: a survey circa 1991. In A. Kent and J. G. Williams, editors, Encyclopedia of Computer Science and Technology, Volume 27 (Supplement 12). Marcel Dekker, New York, 1993.

[11]

{HF89} J. Y. Halpern and R. Fagin. Modelling knowledge and action in distributed systems. Distributed Computing, 3(4):159--179, 1989.

Digital Library

[12]

{Hin75} J. Hintikka. Impossible possible worlds vindicated. Journal of Philosophical Logic, 4:475--484, 1975.

[13]

{HM90} J. Y. Halpern and Y. Moses. Knowledge and common knowledge in a distributed environment. Journal of the ACM, 37(3):549--587, 1990. A preliminary version appeared in Proc. 3rd ACM Symposium on Principles of Distributed Computing, 1984.

Digital Library

[14]

{HM92} J. Y. Halpern and Y. Moses. A guide to completeness and complexity for modal logics of knowledge and belief. Artificial Intelligence, 54:319--379, 1992.

Digital Library

[15]

{HMT88} J. Y. Halpern, Y. Moses, and M. R. Tuttle. A knowledge-based analysis of zero knowledge. In Proc. 20th ACM Symp. on Theory of Computing, pages 132--147, 1988.

Digital Library

[16]

{HT93} J. Y. Halpern and M. R. Tuttle. Knowledge, probability, and adversaries. Journal of the ACM, 40(4):917--962, 1993.

Digital Library

[17]

{HV91} J. Y. Halpern and M. Y. Vardi. Model checking vs. theorem proving: a manifesto. In J. A. Allen, R. Fikes, and E. Sandewall, editors, Principles of Knowledge Representation and Reasoning: Proc. Second International Conference (KR '91), pages 325--334. Morgan Kaufmann, San Mateo, CA, 1991.

[18]

{Kon86} K. Konolige. A Deduction Model of Belief. Morgan Kaufmann, San Mateo, CA, 1986.

Digital Library

[19]

{Lev84} H. J. Levesque. A logic of implicit and explicit belief. In Proc. National Conference on Artificial Intelligence (AAAI '84), pages 198--202, 1984.

[20]

{Meg89} N. Megiddo. On computable beliefs of rational machines. Games and Economical Behaviour, 1:144--169, 1989.

[21]

{Mos88} Y. Moses. Resource-bounded knowledge. In M. Y. Vardi, editor, Proc. Second Conference on Theoretical Aspects of Reasoning about Knowledge, pages 261--276. Morgan Kaufmann, San Mateo, CA, 1988.

Digital Library

[22]

{MW86} N. Megiddo and A. Wigderson. On play by means of computing machines. In J. Y. Halpern, editor, Theoretical Aspects of Reasoning about Knowledge: Proc. 1986 Conference, pages 259--274. Morgan Kaufmann, San Mateo, CA, 1986.

Digital Library

[23]

{Ney85} A. Neyman. Bounded complexity justifies cooperation in finitely repated prisoner's dilemma. Economic Letters, pages 227--229, 1985.

[24]

{PR85} R. Parikh and R. Ramanujam. Distributed processing and the logic of knowledge. In R. Parikh, editor, Proc. Workshop on Logics of Programs, pages 256--268, 1985.

Digital Library

[25]

{RK86} S. J. Rosenschein and L. P. Kaelbling. The synthesis of digital machines with provable epistemic properties. In J. Y. Halpern, editor, Theoretical Aspects of Reasoning about Knowledge: Proc. 1986 Conference, pages 83--97. Morgan Kaufmann, San Mateo, CA, 1986.

Digital Library

[26]

{RSA78} R. L. Rivest, A. Shamir, and L. Adelman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120--126, 1978.

Digital Library

[27]

{Rub85} A. Rubinstein. Finite automata play the repeated prisoner's dilemma. ST/ICERD Discussion Paper 85/109, London School of Economics, 1985.

[28]

{Sho93} Y. Shoham. Agent oriented programming. Artificial Intelligence, 60(1):51--92, 1993.

Digital Library

[29]

{Tho61} E. O. Thorp. A favorable strategy for twenty-one. Proc. Natl. Acad. Sci., 47(1):110--112, 1961.

[30]

{Tho66} E. O. Thorp. Beat the dealer. Vintage, New York, 2nd edition, 1966.

Cited By

Jamroga WTabatabaei M(2013)Accumulative Knowledge under Bounded ResourcesProceedings of the 14th International Workshop on Computational Logic in Multi-Agent Systems - Volume 814310.1007/978-3-642-40624-9_13(206-222)Online publication date: 16-Sep-2013
https://dl.acm.org/doi/10.1007/978-3-642-40624-9_13
Chong S(2012)Required information releaseJournal of Computer Security10.5555/2595038.259504020:6(637-676)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.5555/2595038.2595040
Keshmiri SPayandeh S(2011)Toward opportunistic collaboration in target pursuit problemsProceedings of the Second international conference on Autonomous and intelligent systems10.5555/2026956.2026961(31-40)Online publication date: 22-Jun-2011
https://dl.acm.org/doi/10.5555/2026956.2026961
Show More Cited By

Algorithmic knowledge
1. Theory of computation

Recommendations

Deductive Algorithmic Knowledge

The framework of algorithmic knowledge assumes that agents use algorithms to compute the facts they explicitly know. In many cases of interest, a deductive system, rather than a particular algorithm, captures the formal reasoning used by the agents to ...
An algorithmic approach to knowledge evolution

Intelligent agents must update their knowledge base as they acquire new information about their environment. The modal logic S5ⁿ has been designed for representing knowledge bases in societies of agents. Halpern and Vardi have proposed the notion of ...
Perspective---Tacit Knowledge and Knowledge Conversion: Controversy and Advancement in Organizational Knowledge Creation Theory

Nonaka's paper [1994. A dynamic theory of organizational knowledge creation. Organ. Sci.5(1) 14--37] contributed to the concepts of “tacit knowledge” and “knowledge conversion” in organization science. We present work that shaped the development of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

TARK '94: Proceedings of the 5th conference on Theoretical aspects of reasoning about knowledge

March 1994

348 pages

ISBN:155860331X

Editor:
Ronald Fagin
IBM Almaden Research Center, San Jose, CA

Publisher

Morgan Kaufmann Publishers Inc.

San Francisco, CA, United States

Publication History

Published: 13 March 1994

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 61 of 177 submissions, 34%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
313
Total Downloads

Downloads (Last 12 months)39
Downloads (Last 6 weeks)7

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jamroga WTabatabaei M(2013)Accumulative Knowledge under Bounded ResourcesProceedings of the 14th International Workshop on Computational Logic in Multi-Agent Systems - Volume 814310.1007/978-3-642-40624-9_13(206-222)Online publication date: 16-Sep-2013
https://dl.acm.org/doi/10.1007/978-3-642-40624-9_13
Chong S(2012)Required information releaseJournal of Computer Security10.5555/2595038.259504020:6(637-676)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.5555/2595038.2595040
Keshmiri SPayandeh S(2011)Toward opportunistic collaboration in target pursuit problemsProceedings of the Second international conference on Autonomous and intelligent systems10.5555/2026956.2026961(31-40)Online publication date: 22-Jun-2011
https://dl.acm.org/doi/10.5555/2026956.2026961
Li ZWang WCheung BHui LSandhu RWong D(2011)Rethinking about guessing attacksProceedings of the 6th ACM Symposium on Information, Computer and Communications Security10.1145/1966913.1966954(316-325)Online publication date: 22-Mar-2011
https://dl.acm.org/doi/10.1145/1966913.1966954
Alechina NLogan BNga NRakib A(2008)Verifying time, memory and communication bounds in systems of reasoning agentsProceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 210.5555/1402298.1402326(736-743)Online publication date: 12-May-2008
https://dl.acm.org/doi/10.5555/1402298.1402326
Halpern JPucella RSamet D(2007)Dealing with logical omniscienceProceedings of the 11th conference on Theoretical aspects of rationality and knowledge10.1145/1324249.1324273(169-176)Online publication date: 25-Jun-2007
https://dl.acm.org/doi/10.1145/1324249.1324273
Lomuscio AWoźna BNakashima HWellman MWeiss GStone P(2006)A complete and decidable security-specialised logic and its application to the TESLA protocolProceedings of the fifth international joint conference on Autonomous agents and multiagent systems10.1145/1160633.1160658(145-152)Online publication date: 8-May-2006
https://dl.acm.org/doi/10.1145/1160633.1160658
Lomuscio AWoźna B(2005)A combination of explicit and deductive knowledge with branching timeProceedings of the Third international conference on Declarative Agent Languages and Technologies10.1007/11691792_12(188-204)Online publication date: 25-Jul-2005
https://dl.acm.org/doi/10.1007/11691792_12
Halpern JPucella RHalpern J(2003)Probabilistic algorithmic knowledgeProceedings of the 9th conference on Theoretical aspects of rationality and knowledge10.1145/846241.846258(118-130)Online publication date: 20-Jun-2003
https://dl.acm.org/doi/10.1145/846241.846258
Koriche FSallantin J(2001)A logical toolbox for knowledge approximationProceedings of the 8th conference on Theoretical aspects of rationality and knowledge10.5555/1028128.1028151(193-205)Online publication date: 8-Jul-2001
https://dl.acm.org/doi/10.5555/1028128.1028151
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents