REASONING ABOUT KNOWLEDGE AND PROBABILITY

被引:263
作者
FAGIN, R
HALPERN, JY
机构
[1] IBM Almaden Research Center, San Jose, CA
[2] IBM Almaden Research Center, San Jose, CA
关键词
THEORY; VERIFICATION; KNOWLEDGE; MODAL LOGIC; NONDETERMINISM VS PROBABILITY; POSSIBLE WORDS; PROBABILISTIC COMMON KNOWLEDGE; PROBABILISTIC KNOWLEDGE; REASONING ABOUT KNOWLEDGE AND PROBABILITY;
D O I
10.1145/174652.174658
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
We provide a model for reasoning about knowledge and probability together. We allow explicit mention of probabilities in formulas, so that our language has formulas that essentially say ''according to agent i, formula phi holds with probability at least b.'' The language is powerful enough to allow reasoning about higher-order probabilities, as well as allowing explicit comparisons of the probabilities an agent places on distinct events. We present a general framework for interpreting such formulas, and consider various properties that might hold of the interrelationship between agents' probability assignments at different states. We provide a complete axiomatization for reasoning about knowledge and probability, prove a small model property, and obtain decision procedures. We then consider the effects of adding common knowledge and a probabilistic variant of common knowledge to the language.
引用
收藏
页码:340 / 367
页数:28
相关论文
共 38 条
[11]   THE KNOWLEDGE COMPLEXITY OF INTERACTIVE PROOF SYSTEMS [J].
GOLDWASSER, S ;
MICALI, S ;
RACKOFF, C .
SIAM JOURNAL ON COMPUTING, 1989, 18 (01) :186-208
[12]  
Halmos P.R., 1950, MEASURE THEORY
[13]  
Halpern J. Y., 1989, Computational Intelligence, V5, P151, DOI 10.1111/j.1467-8640.1989.tb00325.x
[14]  
Halpern J. Y., 1991, Annals of Mathematics and Artificial Intelligence, V4, P301, DOI 10.1007/BF01531062
[15]   A LOGIC TO REASON ABOUT LIKELIHOOD [J].
HALPERN, JY ;
RABIN, MO .
ARTIFICIAL INTELLIGENCE, 1987, 32 (03) :379-405
[16]   KNOWLEDGE, PROBABILITY, AND ADVERSARIES [J].
HALPERN, JY ;
TUTTLE, MR .
JOURNAL OF THE ACM, 1993, 40 (04) :917-962
[17]   A GUIDE TO COMPLETENESS AND COMPLEXITY FOR MODAL-LOGICS OF KNOWLEDGE AND BELIEF [J].
HALPERN, JY ;
MOSES, Y .
ARTIFICIAL INTELLIGENCE, 1992, 54 (03) :319-379
[18]   KNOWLEDGE AND COMMON KNOWLEDGE IN A DISTRIBUTED ENVIRONMENT [J].
HALPERN, JY ;
MOSES, Y .
JOURNAL OF THE ACM, 1990, 37 (03) :549-587
[19]   USING REASONING ABOUT KNOWLEDGE TO ANALYZE DISTRIBUTED SYSTEMS [J].
HALPERN, JY .
ANNUAL REVIEW OF COMPUTER SCIENCE, 1987, 2 :37-68
[20]  
HALPERN JY, 1988, 20TH P ACM S THEOR C, P132