Affordable Access

Deductive Algorithmic Knowledge

Authors
  • Pucella, Riccardo
Type
Published Article
Publication Date
Jan 18, 2006
Submission Date
May 11, 2004
Identifiers
arXiv ID: cs/0405038
Source
arXiv
License
Unknown
External links

Abstract

The framework of algorithmic knowledge assumes that agents use algorithms to compute the facts they explicitly know. In many cases of interest, a deductive system, rather than a particular algorithm, captures the formal reasoning used by the agents to compute what they explicitly know. We introduce a logic for reasoning about both implicit and explicit knowledge with the latter defined with respect to a deductive system formalizing a logical theory for agents. The highly structured nature of deductive systems leads to very natural axiomatizations of the resulting logic when interpreted over any fixed deductive system. The decision problem for the logic, in the presence of a single agent, is NP-complete in general, no harder than propositional logic. It remains NP-complete when we fix a deductive system that is decidable in nondeterministic polynomial time. These results extend in a straightforward way to multiple agents.

Report this publication

Statistics

Seen <100 times