LPDA: Another look at Tabulation in Logic Programming
Eric Villemonte de La Clergerie, Bernard Lang · The MIT Press eBooks · 1994
The Logic Push-Down Automaton (LPDA) is introduced as an abstract operational model for the evaluation of logic programs. The LPDA can be used to describe a significant number of evaluation strategies, ranging from the top-down OLD strategy to bottom-up strategies, with or without prediction. Two types of dynamic programming, i.e. tabular, interpretation are defined, one being more efficient but restricted to a subclass of LPDAs. We propose to evaluate a logic program by first compiling it into a LPDA according to some chosen evaluation strategy, and then applying a tabular interpreter to this LPDA. This approach offers great flexibility and generalizes Magic Set transformations. It explains in a more intuitive way some known Magic Set variants and their limits, and also suggests new developments. Keywords: logic programs, tabulation, memoing, magic-set, dynamic programming, push-down automata. 1 Introduction The recent years have seen the popularity of (at least) two approaches to i...