Abstract:
Tabled resolution improves efficiency as well as termination properties of logic programs by sharing answer computations across ``similar'' subgoals. Similarity based on subsumption of subgoals rather than variance (i.e., identity modulo variable renaming) promotes more aggressive sharing, but requires mechanisms to index answers from dynamically growing sets. Earlier we proposed Dynamic Threaded Sequential Automata (DTSA) as the data structure for organizing answer tables in subsumption-based tabling. Using a DTSA, we can retrieve answers one at a time from the table, strictly in the order of their insertion. Although DTSA performed very well, its space usage was high. Here we present an alternative data structure called Time-Stamped Trie (TST) that relaxes the retrieval order, and yet ensures that all answers will be eventually retrieved. We show that TST has superior space performance to DTSA in theory as well as practice, without sacrificing time performance.
Bibtex Entry:
@inproceedings{JRRR:FLOPS99, author = {Ernie Johnson and C. R. Ramakrishnan and I. V. Ramakrishnan and Prasad Rao}, title = {A Space Efficient Engine for Subsumption-Based Tabled Evaluation of Logic Programs}, booktitle = {Fuji International Symposium on Functional and Logic Programming ({FLOPS})}, address = {Tsukuba, Japan}, month = {November}, series = {Lecture Notes in Computer Science}, volume = {1722}, publisher = {Springer}, pages = {284--300}, year = {1999} }
| Full Paper: | [pdf] |
C. R. Ramakrishnan
(cram@cs.sunysb.edu)