Deductive Algorithmic Knowledge

DOI10.1093/LOGCOM/EXI078zbMATH Open1102.03010arXivcs/0405038OpenAlexW1985022920MaRDI QIDQ5477459FDOQ5477459

Riccardo Pucella

Publication date: 3 July 2006

Published in: Journal Of Logic And Computation (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/cs/0405038

zbMATH Keywords

deductive systemsepistemic logicaxiomatizationsexplicit knowledge

Mathematics Subject Classification ID

Logics of knowledge and belief (including belief change) (03B42) Logic in artificial intelligence (68T27)

Cited In (6)

• Dealing with logical omniscience: expressiveness and pragmatics
• Belief ascription under bounded resources
• Verifying time, memory and communication bounds in systems of reasoning agents
• Autoepistemic answer set programming
• To know or not to know: Epistemic approaches to security protocol verification
• The interrogative model of inquiry meets dynamic epistemic logics

   Recommendations

• Probabilistic Algorithmic Knowledge 👍 👎
• Title not available (Why is that?) 👍 👎
• A logico-algebraic approach to the model theory of knowledge 👍 👎
• A logic of knowledge based on abstract arguments 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Deductive Algorithmic Knowledge

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5477459)