Reasoning about knowledge and probability

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Reasoning about knowledge and probability

Full text

Pdf (2.23 MB)

Source

Journal of the ACM (JACM) archive
Volume 41 , Issue 2 (March 1994) table of contents

Pages: 340 - 367

Year of Publication: 1994

ISSN:0004-5411

Authors

Ronald Fagin	IBM Almaden Research Center, San Jose, CA
Joseph Y. Halpern	IBM Almaden Research Center, San Jose, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 86, Citation Count: 29

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/174652.174658 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	~AUMANN, R. J., 1976. Agreeing to disagree. Ann. Stat. 4, 6, 1236 1239.
	2	~CAVE, J. 1983. Learning to agree. Econ. Lett. 12, 147 152.
	3	R. Fagin , Joseph Y. Halpern , Nimrod Megiddo, A logic for reasoning about probabilities, Information and Computation, v.87 n.1-2, p.78-128, July/August 1990 [doi>10.1016/0890-5401(90)90060-U]
	4	Yishai A Feldman, A decidable propositional dynamic logic with explicit probabilities, Information and Control, v.63 n.1-2, p.11-38, Oct/Nov. 1984 [doi>10.1016/S0019-9958(84)80039-X]
	5	~FELLER, W. i957. An Introduction to Probab&tv TheoO' and Its Apphcatlons, volume 1. Wfiey, ~New York.
	6	~fISCHER, M. J. AND LADNER, R E., 1979. Propositional dynamic logic of regular programs. J. ~Comput. Svst. Scl. 18, 2, 194-211.
	7	~FISCHER, M. J. AND ZUCK, k. D., 1987. Relatwe knowledge and belief (extended abstract). Tech. ~Rep. YALEU/DCS/TR-589. Yale Univ.
	8	~FISCHER, M. J. AND ZUCK, L. D., 1988. Reasoning about uncertainty in fault-tolerant distributed ~systems. Tech. Rep. YALEU/DCS/TR-643. Yale Univ.
	9	H Gaifman, A theory of higher order probabilities, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.275-292, March 1986, Monterey, California, United States
	10	S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
	11	~HALMOS, P., 1950. Measure Theory. Van Nostrand, New York.
	12	~HALPERN, J. Y., 1987. Using reasoning about knowledge to analyze distributed systems. In ~Annual Redew of Computer Science, vol. 2. J. F. Traub, B. J. Grosz, B. W. Lampson, and N. J. ~Nilsson, eds. Annual Reviews Inc., Palo Alto, Calif., pp. 37-68.
	13	~HALPERN, J. Y., 1991. The relationship between knowledge, belief, and certainty. Ann. Math. ~Artif. Int. 4, 301-322.
	14	Joseph Y. Halpern , David A. McAllester, Likelihood, probability, and knowledge, Computational Intelligence, v.5 n.3, p.151-160, Aug. 1990 [doi>10.1111/j.1467-8640.1989.tb00325.x]
	15	Joseph Y. Halpern , Yoram Moses, Knowledge and common knowledge in a distributed environment, Journal of the ACM (JACM), v.37 n.3, p.549-587, July 1990 [doi>10.1145/79147.79161]
	16	Joseph Y. Halpern , Yoram Moses, A guide to completeness and complexity for modal logics of knowledge and belief, Artificial Intelligence, v.54 n.3, p.319-379, April 1992 [doi>10.1016/0004-3702(92)90049-4]
	17	Joseph Halpern , Yjoram Moses , Mark Tuttle, A knowledge-based analysis of zero knowledge, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.132-147, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62224]
	18	Joseph Y. Halpern , Michael O. Rabin, A logic to reason about likelihood, Artificial Intelligence, v.32 n.3, p.379-405, July 1987 [doi>10.1016/0004-3702(87)90093-2]
	19	Joseph Y. Halpern , Mark R. Tuttle, Knowledge, probability, and adversaries, Journal of the ACM (JACM), v.40 n.4, p.917-960, Sept. 1993 [doi>10.1145/153724.153770]
	20	Sergiu Hart , Micha Sharir(, Probabilistic temporal logics for finite and bounded models, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.1-13, December 1984 [doi>10.1145/800057.808660]
	21	~HINTIKKA, J., 1962. Knowledge and Belief: Cornell University Press, Ithaca, NY.
	22	~HUGHES, G. E. AND CRESSWELL, M. J., 1968. An Inu'oduction to Modal Logic. Methuen, London.
	23	~KOZEN, D., 1985. Probabilistic PDL. J. Comput. Syst. Sct. 30, 162-178.
	24	~KRIPKE, S., 1963. A semantical analysis of modal logic. I: Normal modal propositional calculi. Z. ~Math. Logik Grundl. Math. 9, 67-96. (Announced in J. Syrnb. Logic 24, 1959, p. 323.)
	25	~LADNER, R. E., 1977. The computational complexity of provability in systems of modal proposi- ~tional logic. SIAM J. Conlput. 6, 3, 467-480.
	26	~LEHMANN, D. AND SHELAH, S., 1982. Reasoning about time and change. Inf. Control 53, ~165-198.
	27	~LENZEN, W., 1978. Recent work m epistemic logic. Acta Phil. Fen. 30, 1-219.
	28	~MAKINSON, D., 1966. On some completeness theorems in modal logic. Z. Math. Logik Gnmdl. ~Math. 12, 379-384.
	29	~MILLER, D., 1966. A paradox of information. Brit. J. Phil. Sci., 17.
	30	~MONDERER, D. AND SAMET, m., 1989. Approximating common knowledge with common beliefs. ~Games and Economic Behat,ior 1, 170-190.
	31	~MOORE, R. C., 1985. A formal theory of knowledge and action. In Fomlal Theories of the ~Commonsense World, J. Hobbs and R. C. Moore, eds. Ablex Publishing Corp., Norwood, N.J., ~pp. 319-358.
	32	Yoram Moses, Resource-bounded Knowledge, Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, p.261-275, March 01, 1988
	33	NEVEU, J., 1964. Bases Mathemattques du Calcul des Probabiht~s. Mason.
	34	Nils J. Nilsson, Probabilistic logic, Artificial Intelligence, v.28 n.1, p.71-88, Feb. 1986 [doi>10.1016/0004-3702(86)90031-7]
	35	~PRATt, V. R., 1979. Models of program logics. In Proceedtngs of the 20th IEEE Symposium on ~Foundations of Computer Science. IEEE, New York, pp. 115-122.
	36	~RUSPINI, E. n., 1987. Epistemic logics, probability, and the calculus of evidence. In Proceedings ~of the l Oth International Joint Conference on Artificial Intelligence ( IJCAI-87 ), pp. 924 931.
	37	~SHAFER, G., 1976. A Mathematical Theory of Et~idence. Princeton University Press, Princeton, ~N.J.
	38	~SKYRMS, B., 1980. Higher order degrees of belief. In Prospects for Pragmatism: Essays in Honor of ~F. P. Ramso'. D. H. Mellor, ed., Cambridge University Press, Cambridge, U.K.

CITED BY 29

	Thomas Rölleke , Norbert Fuhr, Retrieval of complex objects using a four-valued logic, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.206-214, August 18-22, 1996, Zurich, Switzerland
	Boris Galitsky, Merging deductive and inductive reasoning for processing textual descriptions of inter-human conflicts, Journal of Intelligent Information Systems, v.27 n.1, p.21-48, July 2006
	Joseph Y. Halpern, Characterizing the common prior assumption, Proceedings of the 7th conference on Theoretical aspects of rationality and knowledge, July 22-24, 1998, Evanston, Illinois
	Barteld P. Kooi, Probabilistic Dynamic Epistemic Logic, Journal of Logic, Language and Information, v.12 n.4, p.381-408, Fall 2003
	Andreas Herzig, Modal probability, belief, and actions, Fundamenta Informaticae, v.57 n.2-4, p.323-344, October 2003
	Johan Van Benthem, Conditional Probability Meets Update Logic, Journal of Logic, Language and Information, v.12 n.4, p.409-421, Fall 2003
	Ronald Fagin , Yoram Moses , Joseph Y. Halpern , Moshe Y. Vardi, Common knowledge revisited, Proceedings of the 6th conference on Theoretical aspects of rationality and knowledge, March 17-20, 1996, The Netherlands
	Zi Ning Cao , Chun Yi Shi, Probabilistic belief logic and its probabilistic aumann semantics, Journal of Computer Science and Technology, v.18 n.5, p.571-579, September 2003
	Veselka Boeva , Love Ekenberg, A transition logic for schemata conflicts, Data & Knowledge Engineering, v.51 n.3, p.277-294, December 2004
	Aviad Heifetz , Philippe Mongin, The modal logic of probability, Proceedings of the 7th conference on Theoretical aspects of rationality and knowledge, July 22-24, 1998, Evanston, Illinois
	Cristiano Castelfranchi , Luca Tummolini, Positive and negative expectations and the deontic nature of social conventions, Proceedings of the 9th international conference on Artificial intelligence and law, June 24-28, 2003, Scotland, United Kingdom
	James W. Gray, III , Paul F. Syverson, A logical approach to multilevel security of probabilistic systems, Distributed Computing, v.11 n.2, p.73-90, April 1998
	Martin Meier, Harsanyi type spaces with knowledge operators, Proceedings of the 10th conference on Theoretical aspects of rationality and knowledge, June 10-12, 2005, Singapore
	Nivea de Carvalho Ferreira , Michael Fisher , Wiebe van der Hoek, Specifying and reasoning about uncertain agents, International Journal of Approximate Reasoning, v.49 n.1, p.35-51, September, 2008
	Anatol Slissenko, A Logic Framework for Verification of Timed Algorithms, Fundamenta Informaticae, v.62 n.1, p.29-67, January 2004
	Thorsten Clausing, A Syntactic Framework with Probabilistic Beliefs and Conditionals for the Analysis of Strategic Form Games, Journal of Logic, Language and Information, v.11 n.3, p.335-348, Summer 2002
	Ron van der Meyden , Thomas Wilke, Preservation of epistemic properties in security protocol implementations, Proceedings of the 11th conference on Theoretical aspects of rationality and knowledge, June 25-27, 2007, Brussels, Belgium
	Nils Bulling , Wojciech Jamroga, Agents, beliefs, and plausible behavior in a temporal setting, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii
	Joseph Y. Halpern , Riccardo Pucella, Dealing with logical omniscience, Proceedings of the 11th conference on Theoretical aspects of rationality and knowledge, June 25-27, 2007, Brussels, Belgium
	Miodrag Rašković , Zoran Marković , Zoran Ognjanović, A logic with approximate conditional probabilities that can model default reasoning, International Journal of Approximate Reasoning, v.49 n.1, p.52-66, September, 2008
	Evan Tzanis , Robin Hirsch, Probabilistic Logic over Paths, Electronic Notes in Theoretical Computer Science (ENTCS), v.220 n.3, p.79-96, December, 2008
	LUTZ Schröder , Dirk Pattinson, PSPACE bounds for rank-1 modal logics, ACM Transactions on Computational Logic (TOCL), v.10 n.2, p.1-33, February 2009
	Brian Milch, Artificial General Intelligence through Large-Scale, Multimodal Bayesian Learning, Proceeding of the 2008 conference on Artificial General Intelligence 2008: Proceedings of the First AGI Conference, p.248-255, June 20, 2008
	Katarzyna Budzyńska , Magdalena Kacprzak , Paweł Rembelski, Modeling Persuasiveness: change of uncertainty through agents' interactions, Proceeding of the 2008 conference on Computational Models of Argument: Proceedings of COMMA 2008, p.85-96, June 21, 2008
	K. S. Ng , J. W. Lloyd , W. T. Uther, Probabilistic modelling, inference and learning using logical theories, Annals of Mathematics and Artificial Intelligence, v.54 n.1-3, p.159-205, November 2008
	Isaac Pinyol , Jordi Sabater-Mir , Pilar Dellunde, Probabilistic Dynamic Belief Logic for Image and Reputation, Proceeding of the 2008 conference on Artificial Intelligence Research and Development: Proceedings of the 11th International Conference of the Catalan Association for Artificial Intelligence, p.197-205, July 03, 2008
	Joseph Y. Halpern , Riccardo Pucella, A logic for reasoning about evidence, Journal of Artificial Intelligence Research, v.26 n.1, p.1-34, May 2006
	Alberto Finzi , Fiora Pirri, Combining probabilities, failures and safety in robot control, Proceedings of the 17th international joint conference on Artificial intelligence, p.1331-1336, August 04-10, 2001, Seattle, WA, USA
	Isaac Pinyol , Jordi Sabater-Mir, Pragmatic-strategic reputation-based decisions in BDI agents, Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems, May 10-15, 2009, Budapest, Hungary

INDEX TERMS

Primary Classification:
I. Computing Methodologies
I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Languages, Theory, Verification

Keywords:
knowledge, modal logic, nondeterminism vs. probability, possible words, probabilistic common knowledge, probabilistic knowledge, reasoning about knowledge and probability

REVIEW

"Calin Lucaciu : Reviewer"

The way toward a model for reasoning about knowledge and probability begins in this paper with a review of classical possible-worlds semantics for knowledge. Next, the authors provide an extended language and a complete axiomatization for know more...

Collaborative Colleagues:

Ronald Fagin: colleagues

Joseph Y. Halpern: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player