Open AccessImproving Execution Models of Logic Programs by Two‐phase Abstract Interpretation
Author(s) -
Chang ByeongMo,
Choe KwangMoo,
Giacobazzi Roberto
Publication year - 1995
Publication title -
etri journal
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.295
H-Index - 46
eISSN - 2233-7326
pISSN - 1225-6463
DOI - 10.4218/etrij.95.0195.0003
Subject(s) - computer science , abstract interpretation , interpretation (philosophy) , abstraction , logic program , programming language , function (biology) , process (computing) , theoretical computer science , algorithm , logic programming , philosophy , epistemology , evolutionary biology , biology
This paper improves top‐down execution models of logic programs based on a two‐phase abstract interpretation which consists of a bottom‐up analysis followed by a top‐down one. The two‐phase analysis provides an approximation of all (possibly non‐ground) success patterns of clauses relevant to a query. It is specialized by considering Sato and Tamaki's depth k abstraction as abstract function. By the ability of the analysis to approximate possibly non‐ground success patterns of clauses relevant to a query, it can be statically determined whether some subgoals will fail during execution and some succeeding subgoals do not participate in success patterns of program clauses relevant to a given query. These properties are utilized to improve execution models. This approach can be easily applied to any top‐down (parallel) execution models. As instances, it is shown to be applicable to linear execution model and AND/OR Process Model.