Foundations of Equational Logic Programming

✍ Scribed by Steffen Hölldobler (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 1989
• Tongue: English
• Leaves: 261
• Series: Lecture Notes in Computer Science 353 : Lecture Notes in Artificial Intelligence
• Edition: 1
• Category: Library

✦ Synopsis

Equations play a vital role in many fields of mathematics, computer science, and artificial intelligence. Therefore, many proposals have been made to integrate equational, functional, and logic programming. This book presents the foundations of equational logic programming. After generalizing logic programming by augmenting programs with a conditional equational theory, the author defines a unifying framework for logic programming, equation solving, universal unification, and term rewriting. Within this framework many known results are developed. In particular, a presentation of the least model and the fixpoint semantics of equational logic programs is followed by a rigorous proof of the soundness and the strong completeness of various proof techniques: SLDE-resolution, where a universal unification procedure replaces the traditional unification algorithm; linear paramodulation and special forms of it such as rewriting and narrowing; complete sets of transformations for conditional equational theories; and lazy resolution combined with any complete set of inference rules for conditional equational theories.

✦ Table of Contents

Title Page
Copyright Page
Preface
Contents
1 Introduction
2 Preliminaries
2.1 Terms, Atoms, and Equations
2.2 Substitutions
3 Equational Logic Programming
3.1 Equational Logic Programs
3.2 Model Theory
3.3 Fixpoint Theory
3.4 Proof Theory
3.4.1 Unification
3.4.2 SLD-Resolution
4 Universal Unification
5 SLDE-Resolution
6 Paramodulation
6.1 Fixpoint Characterization
6.2 Paramodulation
6.3 Confluent Theories
6.4 Term Rewriting Systems
6.5 Narrowing
6.5.1 Canonical Term Rewriting Systems
6.5.2 Narrowing and Rewriting
6.5.3 Completely Defined Term Rewriting Systems
6.6 The Unification and Matching Problem for Canonical Theories
6.6.1 A Decidability Metatheorem
6.6.2 The Undecidability of the Unification and Matching Problem
6.7 Summary
7 Universal Unification by Complete Sets of Transformations
7.1 The Transformation Rules
7.2 Soundness of the Transformation Rules
7.3 Completeness of the Transformation Rules
8 Lazy Resolution and Complete Sets of Inference Rules for Horn Equational Theories
9 Conclusion
9.1 Summary
9.2 Discussion
E-resoIution
Resolution by Unification and Equality
Equality Graphs
Special Predicates
Flattening
EQLOG
Constraint Logic Programming
CHIP - Constraint Handling in PROLOG
Order-Sorted Horn Logic
LIFE
Theory Resolution
9.3 Open Problems
References
Index
The Inference Rules
Examples
Notations