article

Free access

What can machines know?: On the properties of knowledge in distributed systems

Authors:

Ronald Fagin,

Joseph Y. Halpern,

Moshe Y. VardiAuthors Info & Claims

Journal of the ACM (JACM), Volume 39, Issue 2

Pages 328 - 376

https://doi.org/10.1145/128749.150945

Published: 01 April 1992 Publication History

PDF eReader

References

[1]

BRACHMAN, R., AND LEVESQUE, H. Readings in Knowledge Representation. Morgan- Kaufmann, San Mateo, Calif., 1985.

Crossref

Google Scholar

[2]

CHANDY, K. M., AND MISRA, J. How processes learn. Dist. Comput. I, 1 (t986), 40-52.

Crossref

Google Scholar

[3]

DWORK, C., AND MOSES, Y. Knowledge and common knowledge in a Byzantine environment. I: Crash failures. Inf. Computation 88, 2 (1990), 156-186.

Crossref

Google Scholar

[4]

EMERSON, E.A. Alternative semantics for temporal logics. Theoret. Cornput. Scz. 26 (1983), 121-130.

Google Scholar

[5]

FAGIN, R., AND HALPERN, J. Y. Belief, awareness, and limited reasoning. Artif. b~t. 34 (1988), 39-76.

Crossref

Google Scholar

[6]

FAGIN, R., HALPERN, J. Y., AND VARDI, M.Y. What can machines know? On the epistemic properties of machines. In Proceedings of National Conference on Artificial huelligence ( AAAI- 86). 1986, pp. 428-434.

Google Scholar

[7]

FAGIN, R., AND VARDI, M.Y. An internal semantics for modal logic. In Proceedmgs of the 17th Annual ACM Symposium on Theory of Computing (Providence, R.I., May 6-8). ACM, New York, 1985, pp. 305-315.

Crossref

Google Scholar

[8]

FAGIN, R., AND VARDI, M.Y. Knowledge and implicit knowledge in a distributed environment. In J. Y. Halpern, ed., Theoretical Aspects" of Reasoning about Knowledge. Morgan-Kaufmann, San Mateo, Calif., 1986, pp. 187-206.

Crossref

Google Scholar

[9]

FISCHER, M. J., AND IMMERMAN, N. Foundations of knowledge for distributed systems. In J. Y. Halpern, ed., Theoretical Aspects of Reasoning about Knowledge. Morgan-Kaufmann, San Mateo, Calif., 1986, pp. 171-186.

Crossref

Google Scholar

[10]

HALPERN, J. Y., AND FAGIN, R. Modelling knowledge and action in distributed systems. Dist. Comput. 3, 4 (t989), 159-179.

Google Scholar

[11]

HALPERN, J. Y., AND MOSES, Y. 0. Knowledge and common knowledge in a distributed environment. J. ACM 37, 3 (July 1990), 549-587.

Crossref

Google Scholar

[12]

HALPERN, J. Y., AND MOSES, Y.O. A guide to the modal logics of knowledge and belief. In Proceedings of the 9th International Joint Conference on Artificial h~teIligence (1JCAI-85). 1985, pp. 480-490. (Also, Artif. Int., to appear.)

Google Scholar

[13]

HALPERN, J. Y., AND VARDI, M.Y. The complexity of reasoning about knowledge and time. I: Lower bounds. J. Comput. Syst. Sci. 38 (1989), 195-237.

Crossref

Google Scholar

[14]

HALPERN, J. Y., AND VARDI, M.Y. Reasoning about knowledge and time in asynchronous systems. In Proceedings of the 20th Anmtal ACM Symposium on Theory of Computing (Chicago, ill. May 2-4). ACM, New York, 1988, pp. 53-65.

Crossref

Google Scholar

[15]

HINTIKKA, J. Knowledge and Belief. Cornell University Press, Ithaca, N.Y., t962.

Google Scholar

[16]

KRIPKE, S. Semantical analysis of modal logic. Z. Math. Log. Grund. Math. 9 (1963), 67-96.

Google Scholar

[17]

LADNER, R., AND REIF, J. H. The logic of distributed protocols. In J. Y. Halpern, ed., Theoretical Aspects of Reasoning about Knowledge. Morgan-Kaufmann, San Mateo, Calif., 1986, pp. 207-221.

Crossref

Google Scholar

[18]

LEHMANN, D. Knowledge, common knowledge, and related puzzles. In Proceedings of the 3rd Annual ACM Symposium on Pt4ncipIes of Distributed Computing. ACM, New York, 1984, pp. 467-480.

Crossref

Google Scholar

[19]

LEVESOUV, H. A logic of implicit and explicit belief. In Proceedings of the National Conference on Artificial hzteIligence ( AAAI-84). 1984, pp. 198-202.

Google Scholar

[20]

MAKINSON, D. On some completeness theorems in modal logic. Z. Math. Log. Grund. Math. 12 (1966), 379-384.

Google Scholar

[21]

MOORE, R.C. Reasoning about knowledge and action. Tech. Note 191. Artificial intelligence Center, SRI International, Menlo Park, Calif., 1980.

Google Scholar

[22]

MOSES, Y., AND TUTTLE, M. Programming simultaneous actions using common knowledge. AIgorithmtca 3 (1988), 121-169.

Google Scholar

[23]

PARIKH, R., AND RAMANUJAM, R. Distributed processing and the logic of knowledge. In Proceedings of the Workshop on Logics of Programs (Brooklyn, N.Y., June). Lecture Notes in Computer Science, vol. 193. Springer-Verlag, New York, 1985, pp. 256-268.

Crossref

Google Scholar

[24]

PRATT, V.R. Process logic. In Proceedings of tlze 6th Annztal ACM Symposmm on Prmctples of Programming Languages. (San Antanio, Tex., Jan. 29-31). ACM, New York, 1979, pp. 93-100.

Crossref

Google Scholar

[25]

ROSENSCHEIN, S. J. Formal theories of knowledge in AI and robotics. New Generation Comput. 3 (1985) 345-357.

Crossref

Google Scholar

[26]

ROSENSCHF, IN, S. J., AND KAEU3LING, L.P. The synthesis of digital machines with provable epistemlc properties. In J. Y. Halpern, ed., Theorencal Aspects of Reasonmg about Ka~owledge. Morgan-Kaufmann, San Mateo, Calif., 1986, pp. 83-98.

Crossref

Google Scholar

[27]

SAVAGE, k.J. The Foundations of Statistics. Wiley, New York, 1954.

Google Scholar

Cited By

View all

Jiang JNaumov P(2025)De re/de dicto distinction: a logicians’ perspective on data anonymityJournal of Cybersecurity10.1093/cybsec/tyae02511:1Online publication date: 21-Jan-2025
https://doi.org/10.1093/cybsec/tyae025
Jiang JNaumov PWooldridge MDy JNatarajan S(2024)The logic of doxastic strategiesProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i18.29963(19876-19883)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i18.29963
Goubault ÉKniazev RLedent JRajsbaum S(2024)Simplicial models for the epistemic logic of faulty agentsBoletín de la Sociedad Matemática Mexicana10.1007/s40590-024-00656-x30:3Online publication date: 9-Sep-2024
https://doi.org/10.1007/s40590-024-00656-x
Show More Cited By

Index Terms

Recommendations

Wavelet twin support vector machines based on glowworm swarm optimization

Twin support vector machine is a machine learning algorithm developing from standard support vector machine. The performance of twin support vector machine is always better than support vector machine on datasets that have cross regions. Recently ...
PAC-Bayes bounds for twin support vector machines

Twin support vector machines are regarded as a milestone in the development of support vector machines. Compared to standard support vector machines, they learn two nonparallel hyperplanes rather than one as in standard support vector machines for ...
Multitask centroid twin support vector machines

Twin support vector machines are a recently proposed learning method for binary classification. They learn two hyperplanes rather than one as in conventional support vector machines and often bring performance improvements. However, an inherent shortage ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 39, Issue 2

April 1992

196 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/128749

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1992

Published in JACM Volume 39, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

105
Total Citations
View Citations
1,004
Total Downloads

Downloads (Last 12 months)144
Downloads (Last 6 weeks)25

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Jiang JNaumov P(2025)De re/de dicto distinction: a logicians’ perspective on data anonymityJournal of Cybersecurity10.1093/cybsec/tyae02511:1Online publication date: 21-Jan-2025
https://doi.org/10.1093/cybsec/tyae025
Jiang JNaumov PWooldridge MDy JNatarajan S(2024)The logic of doxastic strategiesProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i18.29963(19876-19883)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i18.29963
Goubault ÉKniazev RLedent JRajsbaum S(2024)Simplicial models for the epistemic logic of faulty agentsBoletín de la Sociedad Matemática Mexicana10.1007/s40590-024-00656-x30:3Online publication date: 9-Sep-2024
https://doi.org/10.1007/s40590-024-00656-x
Jiang JNaumov P(2024)A logic of trust-based beliefsSynthese10.1007/s11229-024-04671-3204:2Online publication date: 18-Jul-2024
https://doi.org/10.1007/s11229-024-04671-3
Galimullin RVelázquez-Quesada F(2024)Topic-Based Communication Between AgentsStudia Logica10.1007/s11225-024-10119-zOnline publication date: 31-Aug-2024
https://doi.org/10.1007/s11225-024-10119-z
Murai RSano K(2024)Intuitionistic Public Announcement Logic with Distributed KnowledgeStudia Logica10.1007/s11225-023-10066-1112:3(661-691)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s11225-023-10066-1
Deuser KJiang JNaumov PZhang W(2024)A Dynamic Logic of Data-Informed KnowledgeJournal of Philosophical Logic10.1007/s10992-023-09740-553:2(521-557)Online publication date: 16-Jan-2024
https://doi.org/10.1007/s10992-023-09740-5
Epstein SNaumov PTao J(2023)An egocentric logic of de dicto and de re knowing whoJournal of Logic and Computation10.1093/logcom/exad05334:7(1347-1376)Online publication date: 23-Aug-2023
https://doi.org/10.1093/logcom/exad053
Долгоруков В(2022)О трудностях определения имплицитного знания группыLogical Investigations10.21146/2074-1472-2022-28-1-9-2628:1(9-26)Online publication date: 26-Jun-2022
https://doi.org/10.21146/2074-1472-2022-28-1-9-26
Solaki A(2022)Actualizing distributed knowledge in bounded groupsJournal of Logic and Computation10.1093/logcom/exac00733:6(1497-1525)Online publication date: 11-Mar-2022
https://doi.org/10.1093/logcom/exac007
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

References

Cited By

Index Terms

Recommendations

Wavelet twin support vector machines based on glowworm swarm optimization

PAC-Bayes bounds for twin support vector machines

Multitask centroid twin support vector machines

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Share

Share this Publication link

Share on social media

Affiliations