@inproceedings{aede8529216d438fb6818f7c98ce258a,
title = "A space efficient engine for subsumption-based tabled evaluation of logic programs",
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.",
author = "Ernie Johnson and Ramakrishnan, \{C. R.\} and Ramakrishnan, \{I. V.\} and Prasad Rao",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 4th Fuji International Symposium on Functional and Logic Programming, FLOPS 1999 ; Conference date: 11-11-1999 Through 13-11-1999",
year = "1999",
doi = "10.1007/10705424\_19",
language = "English",
isbn = "354066677X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "284--299",
editor = "Aart Middeldorp and Taisuke Sato",
booktitle = "Functional and Logic Programming - 4th Fuji International Symposium, FLOPS 1999, Proceedings",
}