Incremental tabling for query-driven propagation of logic program updates

Ari Saptawijaya, Luís Moniz Pereira

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

6 Citations (Scopus)

Abstract

We foster a novel implementation technique for logic program updates, which exploits incremental tabling in logic programming - using XSB Prolog to that effect. Propagation of updates of fluents is controlled by initially keeping any fluent updates pending in the database. And, on the initiative of queries, making active just those updates up to the timestamp of an actual query, by performing incremental assertions of the pending ones. These assertions, in turn, automatically trigger system-implemented incremental bottom-up tabling of other fluents (or their negated complements), with respect to a predefined overall upper time limit, in order to avoid runaway iteration. The frame problem can then be dealt with by inspecting a table for the latest time a fluent is known to be assuredly true, i.e., the latest time it is not supervened by its negated complement, relative to the given query time. To do so, we adopt the dual program transformation for defining and helping propagate, also incrementally and bottom-up, the negated complement of a fluent, in order to establish whether a fluent is still true at some time point, or rather if its complement is. The use of incremental tabling in this approach affords us a form of controlled, but automatic, system level truth-maintenance, up to some actual query time. Consequently, propagation of update side-effects need not employ top-down recursion or bottom-up iteration through a logically defined frame axiom, but can be dealt with by the mechanics of the underlying world. Our approach thus reconciles high-level top-down deliberative reasoning about a query, with autonomous low-level bottom-up world reactivity to ongoing updates, and it might be adopted elsewhere for reasoning in logic.

Original languageEnglish
Title of host publicationLogic for Programming, Artificial Intelligence, and Reasoning - 19th International Conference, LPAR 2013, Proceedings
PublisherSpringer Verlag
Pages694-709
Number of pages16
ISBN (Print)9783642452208
DOIs
Publication statusPublished - 1 Jan 2013
Event19th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2013 - Stellenbosch, South Africa
Duration: 14 Dec 201319 Dec 2013

Publication series

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

Conference

Conference19th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2013
CountrySouth Africa
CityStellenbosch
Period14/12/1319/12/13

Keywords

  • Dual program transformation
  • Incremental tabling
  • Logic program updates
  • Updates propagation
  • XSB prolog

Fingerprint Dive into the research topics of 'Incremental tabling for query-driven propagation of logic program updates'. Together they form a unique fingerprint.

  • Cite this

    Saptawijaya, A., & Pereira, L. M. (2013). Incremental tabling for query-driven propagation of logic program updates. In Logic for Programming, Artificial Intelligence, and Reasoning - 19th International Conference, LPAR 2013, Proceedings (pp. 694-709). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8312). Springer Verlag. https://doi.org/10.1007/978-3-642-45221-5_46