Deductive Algorithmic Knowledge

DOI10.1093/LOGCOM/EXI078MaRDI QIDQ5477459zbMATH OpenOpenAlexFDO

Authors Riccardo Pucella

Publication date 3 July 2006

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

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

zbMATH Keywords

axiomatizationsdeductive systemsepistemic logicexplicit knowledge

Mathematics Subject Classification ID

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

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.

Recommendations

• Probabilistic Algorithmic Knowledge
• scientific article; zbMATH DE number 795590
• A logico-algebraic approach to the model theory of knowledge
• A logic of knowledge based on abstract arguments
• scientific article; zbMATH DE number 3930375

Cited in

(9)

• Verifying time, memory and communication bounds in systems of reasoning agents
• Autoepistemic answer set programming
• Mono-agent dynamics
• The interrogative model of inquiry meets dynamic epistemic logics
• Probabilistic Algorithmic Knowledge
• Dealing with logical omniscience: expressiveness and pragmatics
• To know or not to know: Epistemic approaches to security protocol verification
• Logic of knowledge and discovery via interacting agents -- decision algorithm for true and satisfiable statements
• Belief ascription under bounded resources

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)