Tabling with sound answer subsumption

DOI10.1017/S147106841600048XMaRDI QIDQ4593070zbMATH OpenFDO

Authors Alexander Vandenbroucke, Maciej Piróg, Benoit Desouter, Tom Schrijvers

Publication date 9 November 2017

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

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

zbMATH Keywords

latticepartial orderdenotational semanticsPrologtablinganswer subsumptionmode-directed tabling

Mathematics Subject Classification ID

Logic programming (68N17) Semantics in the theory of computing (68Q55)

Abstract: Tabling is a powerful resolution mechanism for logic programs that captures their least fixed point semantics more faithfully than plain Prolog. In many tabling applications, we are not interested in the set of all answers to a goal, but only require an aggregation of those answers. Several works have studied efficient techniques, such as lattice-based answer subsumption and mode-directed tabling, to do so for various forms of aggregation. While much attention has been paid to expressivity and efficient implementation of the different approaches, soundness has not been considered. This paper shows that the different implementations indeed fail to produce least fixed points for some programs. As a remedy, we provide a formal framework that generalises the existing approaches and we establish a soundness criterion that explains for which programs the approach is sound. This article is under consideration for acceptance in TPLP.

Recommendations

• Tabling with answer subsumption: implementation, applications and performance
• Linear tabling strategies and optimizations
• scientific article; zbMATH DE number 1487801
• scientific article; zbMATH DE number 1332641
• Termination proofs for logic programs with tabling

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 3872640 (Why is no real title available?)
• scientific article; zbMATH DE number 2087342 (Why is no real title available?)
• Abstract interpretation and application to logic programs
• Greedoids
• Partially Ordered Sets
• Tabling for non-monotonic programming
• Tabling with answer subsumption: implementation, applications and performance
• The YAP prolog system
• The language features and architecture of B-Prolog
• XSB: extending Prolog with tabled logic programming

Cited in

(1)

• Tabling with answer subsumption: implementation, applications and performance

Describes a project that uses

Uses Software

• XSB
• B-Prolog
• YAP-Prolog

This page was built for publication: Tabling with sound answer subsumption

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