TY - GEN
T1 - A new formulation of tabled resolution with delay
AU - Swift, Terrance
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1999.
PY - 1999
Y1 - 1999
N2 - Tabling has become important to logic programming in part because it opens new application areas, such as model checking, to logic programming techniques. However, the development of new extensions of tabled logic programming is becoming restricted by the formalisms that underly it. Formalisms for tabled evaluations, such as SLG [3], are generally developed with a view to a specific set of allowable operations that can be performed in an evaluation. In the case of SLG, tabling operations are based on a variance relation between atoms. While the set of SLG tabling operations has proven useful for a number of applications, other types of operations, such as those based on a subsumption relation between atoms, can have practical uses. In this paper, SLG is reformulated in two ways: so that it can be parameterized using different sets of operations; and so that a forest of trees paradigm is used. Equivalence to SLG of the new formulation, Extended SLG or SLGx, is shown when the new formalism is parameterized by variant-based operations. In addition, SLGx is also parameterized by subsumption-based operations and shown correct for queries to the well-founded model. Finally, the usefulness of the forest of trees paradigm for motivating tabling optimizations is shown by formalizing the concept of relevance within a tabled evaluation.
AB - Tabling has become important to logic programming in part because it opens new application areas, such as model checking, to logic programming techniques. However, the development of new extensions of tabled logic programming is becoming restricted by the formalisms that underly it. Formalisms for tabled evaluations, such as SLG [3], are generally developed with a view to a specific set of allowable operations that can be performed in an evaluation. In the case of SLG, tabling operations are based on a variance relation between atoms. While the set of SLG tabling operations has proven useful for a number of applications, other types of operations, such as those based on a subsumption relation between atoms, can have practical uses. In this paper, SLG is reformulated in two ways: so that it can be parameterized using different sets of operations; and so that a forest of trees paradigm is used. Equivalence to SLG of the new formulation, Extended SLG or SLGx, is shown when the new formalism is parameterized by variant-based operations. In addition, SLGx is also parameterized by subsumption-based operations and shown correct for queries to the well-founded model. Finally, the usefulness of the forest of trees paradigm for motivating tabling optimizations is shown by formalizing the concept of relevance within a tabled evaluation.
KW - Logic programming
KW - Non-Monotonic reasoning
UR - http://www.scopus.com/inward/record.url?scp=84957697212&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84957697212&partnerID=8YFLogxK
U2 - 10.1007/3-540-48159-1_12
DO - 10.1007/3-540-48159-1_12
M3 - Conference contribution
AN - SCOPUS:84957697212
SN - 354066548X
SN - 9783540665489
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 163
EP - 177
BT - Progress in Artificial Intelligence - 9th Portuguese Conference on Artificial Intelligence, EPIA 1999, Proceedings
A2 - Barahona, Pedro
A2 - Alferes, José J.
PB - Springer Verlag
T2 - 9th Portuguese Conference on Progress in Artificial Intelligence, EPIA 1999
Y2 - 21 September 1999 through 24 September 1999
ER -