Knowledge compilation of logic programs using approximation fixpoint theory

DOI10.1017/S1471068415000162zbMATH Open1379.68045arXiv1507.06554OpenAlexW3104362192MaRDI QIDQ4592990FDOQ4592990

Authors: Bart Bogaerts, Guy Van den Broeck 

Publication date: 9 November 2017

Published in: Theory and Practice of Logic Programming (Search for Journal in Brave)

Abstract: To appear in Theory and Practice of Logic Programming (TPLP), Proceedings of ICLP 2015 Recent advances in knowledge compilation introduced techniques to compile emph{positive} logic programs into propositional logic, essentially exploiting the constructive nature of the least fixpoint computation. This approach has several advantages over existing approaches: it maintains logical equivalence, does not require (expensive) loop-breaking preprocessing or the introduction of auxiliary variables, and significantly outperforms existing algorithms. Unfortunately, this technique is limited to emph{negation-free} programs. In this paper, we show how to extend it to general logic programs under the well-founded semantics. We develop our work in approximation fixpoint theory, an algebraical framework that unifies semantics of different logics. As such, our algebraical results are also applicable to autoepistemic logic, default logic and abstract dialectical frameworks.

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

Recommendations

• Approximation Fixpoint Theory and the Semantics of Logic and Answers Set Programs
• scientific article; zbMATH DE number 549989
• Knowledge compilation and theory approximation
• scientific article; zbMATH DE number 4106291
• Normal Forms for Knowledge Compilation

Mathematics Subject Classification ID

Logic programming (68N17) Theory of compilers and interpreters (68N20) Logic in artificial intelligence (68T27) Semantics in the theory of computing (68Q55)

Cites Work

• ASSAT: computing answer sets of a logic program by SAT solvers
• Graph-Based Algorithms for Boolean Function Manipulation
• Propositional semantics for disjunctive logic programs
• Title not available (Why is that?)
• The well-founded semantics for general logic programs
• Datalog extensions for database queries and updates
• Knowledge compilation and theory approximation
• On probabilistic inference by weighted model counting
• Well-founded and stable semantics of logic programs with aggregates
• The Semantics of Predicate Logic as a Programming Language
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Tarskian Informal Semantics for Answer Set Programming
• On notation for ordinal numbers
• Inference and learning in probabilistic logic programs using weighted Boolean formulas
• Fixpoint semantics for logic programming a survey
• Approximations, stable operators, well-founded fixpoints and applications in nonmonotonic reasoning
• Ultimate approximation and its application in nonmonotonic knowledge representation systems
• Ordered completion for first-order logic programs on finite structures
• Approximating operators and semantics for abstract dialectical frameworks
• Well-Founded Semantics and the Algebraic Theory of Non-monotone Inductive Definitions
• Why are there so many loop formulas?
• Hex semantics via approximation fixpoint theory
• Some (in)translatability results for normal logic programs and propositional theories
• Computing Stable Models via Reductions to Difference Logic

Cited In (7)

• IASCAR: incremental answer set counting by anytime refinement
• Embedding justification theory in approximation fixpoint theory
• Compact representation of knowledge bases in inductive logic programming
• Alternating Fixpoint Operator for Hybrid MKNF Knowledge Bases as an Approximator of AFT
• A kind of logical compilation for knowledge bases
• \(T_{\mathcal{P}}\)-compilation for inference in probabilistic logic programs
• IASCAR: incremental answer set counting by anytime refinement

Uses Software

• ASSAT

This page was built for publication: Knowledge compilation of logic programs using approximation fixpoint theory

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