Computer Science – Artificial Intelligence
Scientific paper
2004-05-11
Journal of Logic and Computation 16 (2), pp. 287-309, 2006
Computer Science
Artificial Intelligence
28 pages. A preliminary version of this paper appeared in the Proceedings of the 8th International Symposium on Artificial Int
Scientific paper
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.
No associations
LandOfFree
Deductive Algorithmic Knowledge does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Deductive Algorithmic Knowledge, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deductive Algorithmic Knowledge will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-672737