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


Consultation statistics

This page has been seen 40 times.
This article's PDF has been downloaded 20 times.