Article

Free access

Common knowledge and update in finite environments. I: extended abstract

Author:

Ron van der MeydenAuthors Info & Claims

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

Pages 225 - 242

Published: 13 March 1994 Publication History

Abstract

This paper studies the model checking problem for knowledge formulae in the S5<sub><i>n</i></sub> Kripke structures generated by finite state environments in which states determine an observation for each agent. Agents have perfect recall, and may operate synchronously or asynchronously. Common knowledge formulae are shown to be be intractable, but efficient incremental algorithms are developed for formulae containing only knowledge operators. Connections to knowledge updates and compilation of knowledge based protocols are discussed.

References

[1]

{HV88a} J. Halpern and M. Y. Vardi. The complexity of reasoning about knowledge and time: Synchronous systems. Technical Report RJ 6097, IBM Almaden Research Center, 1988.]]

[2]

{HV88b} J. Halpern and M. Y. Vardi. Reasoning about knowledge and time in asynchronous systems. Technical Report RJ 6197, IBM Almaden Research Center, 1988.]]

Digital Library

[3]

{HV89} J. Halpern and M. Y. Vardi. The complexity of reasoning about knowledge and time, I: Lower bounds. Journal of Computer and System Sciences, 38(1):195--237, 1989.]]

Digital Library

[4]

{HV91} J. Halpern and M. Y. Vardi. Model checking vs. theorem proving: A manifesto. Technical Report RJ 7963, IBM Almaden Research Center, 1991. An extended version of a paper in Proc. 2nd Int. Conf. on Principles of Knowledge Representation and Reasoning, 1991.]]

[5]

{HZ92} J. Halpern and L. Zuck. A little knowledge goes a long way: Simple knowledge based derivations and correctness proofs for a family of protocols. Journal of the ACM, 39(3):449--478, 1992.]]

Digital Library

[6]

{IS92} H. Isozaki and Y. Shoham. A mechanism for reasoning about time and belief. In Proc. Int. Conf. on Fifth Generation Computer Systems, pages 694--701, 1992.]]

[7]

{KM91} H. Katsuno and A. Mendelzon. On the difference between updating a knowledge base and revising it. In Proc. 2nd Int. Conf. on Principles of Knowledge Representation and Reasoning, pages 387--394, 1991.]]

[8]

{Koh70} Z. Kohavi. Switching and Finite Automata Theory. McGraw-Hill, New York, 1970.]]

Digital Library

[9]

{LR86} R. Ladner and J. Reif. The logic of distributed protocols. In J. Y. Halpern, editor, Theoretical Aspects of Reasoning about Knowledge: Proc. 1986 Conf., pages 207--222, San Mateo, California, 1986. Morgan Kaufmann.]]

Digital Library

[10]

{Maz86} M. Mazer. A knowledge theoretic account of recovery in distributed systems: The case of negotiated commitment. In M. Y. Vardi, editor, Proc. 2nd Conf. on Theoretical Aspects of Reasoning about Knowledge, pages 207--222, San Mateo, California, 1986. Morgan Kaufmann.]]

Digital Library

[11]

{Mey93a} R. van der Meyden. Axioms for knowledge and time in distributed systems with perfect recall. Technical report, NTT Basic Research Labs, 1993.]]

[12]

{Mey93b} R. van der Meyden. Common knowledge and update in finite environments II: Simple environments. Technical report, NTT Basic Research Labs, 1993.]]

[13]

{MK93} Y. Moses and O. Kislev. Knowledge oriented programming. In Proc. Symposium on Principles of Distributed Computing, 1993.]]

Digital Library

[14]

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

Digital Library

[15]

{PT92} P. Panangaden and K. Taylor. Concurrent common knowledge: defining agreement for asynchronous systems. Distributed Computing, 6:73--93, 1992.]]

Digital Library

[16]

{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 Conf., pages 83--98. Morgan Kaufman, Los Altos, CA, 1986.]]

Digital Library

[17]

{Ros85} S. J. Rosenschein. Formal properties of knowledge in AI and robotics. New Generation Computing, 3:345--357, 1985.]]

Digital Library

[18]

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

Digital Library

[19]

{Val90} A. Valmari. A stubborn attack on state explosion. In Proc. 2nd Workshop on Computer Aided Verification, pages 156--165. Springer LNCS No. 531, 1990.]]

Digital Library

[20]

{Win88} M. Winslett. Reasoning about action using a possible models approach. In Proc. National Conf. on Artificial Intelligence, pages 89--93, 1988.]]

Cited By

van der Meyden R(1996)Knowledge based programsProceedings of the 6th conference on Theoretical aspects of rationality and knowledge10.5555/1029693.1029697(31-49)Online publication date: 17-Mar-1996
https://dl.acm.org/doi/10.5555/1029693.1029697
Ramanujam R(1996)Local knowledge assertions in a changing worldProceedings of the 6th conference on Theoretical aspects of rationality and knowledge10.5555/1029693.1029694(1-14)Online publication date: 17-Mar-1996
https://dl.acm.org/doi/10.5555/1029693.1029694

Common knowledge and update in finite environments. I: extended abstract
1. Theory of computation

Recommendations

On the semantics of knowledge update
IJCAI'01: Proceedings of the 17th international joint conference on Artificial intelligence - Volume 1

We consider the problem of how an agent's knowledge can be updated. We propose a formal method of knowledge update on the basis of the semantics of modal logic S5. In our method, an update is specified according to the minimal change on both the agent's ...
Knowledge and common knowledge in a distributed environment
PODC '84: Proceedings of the third annual ACM symposium on Principles of distributed computing

We argue that the right way to understand distributed protocols is by considering how messages change the state of knowledge of a system. We present a hierarchy of knowledge states that a system may be in, and discuss how communication can move the ...
Knowledge and common knowledge in a distributed environment

Reasoning about knowledge seems to play a fundamental role in distributed systems. Indeed, such reasoning is a central part of the informal intuitive arguments used in the design of distributed protocols. Communication in a distributed system can be ...

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

2
Total Citations
View Citations
195
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)14

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

van der Meyden R(1996)Knowledge based programsProceedings of the 6th conference on Theoretical aspects of rationality and knowledge10.5555/1029693.1029697(31-49)Online publication date: 17-Mar-1996
https://dl.acm.org/doi/10.5555/1029693.1029697
Ramanujam R(1996)Local knowledge assertions in a changing worldProceedings of the 6th conference on Theoretical aspects of rationality and knowledge10.5555/1029693.1029694(1-14)Online publication date: 17-Mar-1996
https://dl.acm.org/doi/10.5555/1029693.1029694

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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