Tabling with answer subsumption: Implementation, applications and performance

Terrance Swift, David S. Warren

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Scopus citations

Abstract

Tabled Logic Programming (TLP) is becoming widely available in Prolog systems, but most implementations of TLP implement only answer variance in which an answer A is added to the table for a subgoal S only if A is not a variant of any other answer already in the table for S. While TLP with answer variance is powerful enough to implement the well-founded semantics with good termination and complexity properties, TLP becomes much more powerful if a mechanism called answer subsumption is used. XSB implements two forms of answer subsumption. The first, partial order answer subsumption, adds A to a table only if A is greater than all other answers already in the table according to a user-defined partial order. The second, lattice answer subsumption, may join A to some other answer in the table according to a user-defined upper semi-lattice. Answer subsumption can be used to implement paraconsistent and quantitative logics, abstract analysis domains, and preference logics. This paper discusses the semantics and implementation of answer subsumption in XSB, and discusses performance and scalability of answer subsumption on a variety of problems.

Original languageEnglish (US)
Title of host publicationLogics in Artificial Intelligence - 12th European Conference, JELIA 2010, Proceedings
Pages300-312
Number of pages13
DOIs
StatePublished - 2010
Externally publishedYes
Event12th European Conference on Logics in Artificial Intelligence, JELIA 2010 - Helsinki, Finland
Duration: Sep 13 2010Sep 15 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6341 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th European Conference on Logics in Artificial Intelligence, JELIA 2010
Country/TerritoryFinland
CityHelsinki
Period9/13/109/15/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Tabling with answer subsumption: Implementation, applications and performance'. Together they form a unique fingerprint.

Cite this