Linear Tabling Strategies and Optimization Techniques

Tabling is a technique that can get rid of innite loops and redundant computations in the execution of recursive logic programs. The main idea of tabling is to memorize the answers to subgoals and use the answers to resolve their variant descendents. Tabling helps narrow the gap between declarative and procedural readings of logic programs. It not only is useful in the problem domains that motivated its birth, such as program analysis, parsing, deductive database, and theorem proving, but also has been found essential in several other problem domains such as model checking, learning, and data mining. Early resolution mechanisms proposed for tabling such as OLDT rely on suspension and resumption of subgoals to compute xpoints. Recently, a new resolution framework called linear tabling, envisioned by the proposer and several other researchers, has received considerable attention because of its simplicity, ease of implementation, and good space eciency. The idea of linear tabling is to use depth-rst iterative deepening rather than suspension to compute xpoints. Linear tabling is still immature compared with OLDT and a great of potential remains to be exploited. The objective of this project is to qualitatively and quantitatively analyze possible strategies and propose eective optimization technique