Upside-down meta-interpretation of the model elimination theorem-proving procedure for deduction and abduction

• Published in: Journal of automated reasoning 1994-01, Vol.13 (2), p.189-210
• Main Author: Stickel, Mark E.
• Format: Article
• Language: English
• ISSN: 0168-7433; 1573-0670
• DOI: 10.1007/BF00881955

Typical bottom-up, forward-chaining reasoning systems such as hyperresolution lack goal-directedness, while typical top-down, backward-chaining reasoning systems like Prolog or model elimination repeatedly solve the same goals. Reasoning systems that are goal-directed and avoid repeatedly solving the same goals can be constructed by formulating the top-down methods meta-theoretically for execution by a bottom-up reasoning system (hence, we use the term upside-down meta-interpretation). This formulation also facilitates the use of flexible search strategies, such as merit-ordered search, that are common to bottom-up reasoning systems. The model elimination theorem-proving procedure, its extension by an assumption rule for abduction, and its restriction to Horn clauses are adapted here for such upside-down meta-interpretation. This work can be regarded as an extension of the magic-sets or Alexander method for query evaluation in deductive databases to both non-Horn clauses and abductive reasoning.