Probabilistic Algorithmic Knowledge

Abstract

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 ' provides evidence for ' being true. Finally, we discuss the extent to which this evidence can be used as a basis for decisions.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 20, 2005
Accession Number
AD1020549

Entities

People

  • Joseph Halpern
  • Riccardo Pucella

Organizations

  • Cornell University

Tags

Communities of Interest

  • Autonomy
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Composite Materials
  • Computer Science
  • Cryptography
  • Electronic Mail
  • Hypotheses
  • Language
  • Literature
  • Models
  • Notation
  • Numbers
  • Probability
  • Probability Distributions
  • Random Variables
  • Security Protocols
  • Semantic Models

Fields of Study

  • Computer science

Readers

  • Computational Linguistics
  • Regression Analysis.