On Improving the Efficiency of Deterministic Calls and Answers in Tabled Logic Programs

Abstract

The execution model on which most tabling engines are based allocates a choice point whenever a new tabled subgoal is called. This happens even when the call is deterministic. However, some of the information from the choice point is never used when evaluating deterministic tabled calls with batched scheduling. Moreover, when a deterministic answer is found for a deterministic tabled call, the call can be completed early and the corresponding choice point can be removed. Thus, if applying batched scheduling to a long deterministic computation, the system may end up consuming memory and evaluating calls unnecessarily. In this paper, we propose a solution that tries to reduce this memory and execution overhead to a minimum. Our experimental results show that, for deterministic tabled calls and tabled answers with batched scheduling, it is possible not only to reduce the memory usage overhead, but also the running time of the execution.

Bibtex

@InProceedings{areias-epia09,
  author =    {M. Areias and R. Rocha},
  title =     {{On Improving the Efficiency of Deterministic Calls and Answers in Tabled Logic Programs}},
  booktitle = {Proceedings of the 14th Portuguese Conference on Artificial Intelligence (EPIA 2009)},
  pages =     {113--125},
  number =    {5816},
  series =    {LNAI},
  publisher = {Springer},
  editor =    {L. S. Lopes and N. Lau and P. Mariano and L. Rocha},
  month =     {October},
  year =      {2009},
  address =   {Aveiro, Portugal},
}

Download Paper

PDF file
Springer