## Halpern, Joseph Y. and Pucella, Riccardo - Probabilistic Algorithmic Knowledge

lmcs:2261 - Logical Methods in Computer Science, December 20, 2005, Volume 1, Issue 3
Probabilistic Algorithmic Knowledge

Authors: Halpern, Joseph Y. and Pucella, Riccardo

The framework of algorithmic knowledge assumes that agents use deterministic knowledge algorithms to compute the facts they explicitly know. We extend the framework to allow for randomized knowledge algorithms. We then characterize the information provided by a randomized knowledge algorithm when its answers have some probability of being incorrect. We formalize this information in terms of evidence; a randomized knowledge algorithm returning Yes'' to a query about a fact \phi provides evidence for \phi being true. Finally, we discuss the extent to which this evidence can be used as a basis for decisions.

Source : oai:arXiv.org:cs/0503018
DOI : 10.2168/LMCS-1(3:1)2005
Volume: Volume 1, Issue 3
Published on: December 20, 2005
Submitted on: March 20, 2005
Keywords: Computer Science - Artificial Intelligence,Computer Science - Logic in Computer Science,I.2.4,G.3