Ebook: Computing in Horn Clause Theories

At least four research fields detennine the theoretical background of specification and deduction in computer science: recursion theory, automated theorem proving, abstract data types and tenn rewriting systems. As these areas approach each other more and more, the strong distinctions between functional and relational views, deductive and denotational approaches as well as between specification and programming are relieved in favour of their integration. The book will not expose the lines of this development; conversely, it starts out from the nucleus of Hom clause logic and brings forth both known and unknown results, most of which affect more than one of the fields mentioned above. Chapter 1 touches on historical issues of specification and prototyping and delimits the topics handled in this book from others which are at the core of related work. Chapter 2 provides the fundamental notions and notations needed for the presentation and interpretation of many-sorted Horn clause theories with equality. Chapter 3 supplies a number of sample Hom clause specifications ranging from arithmetic through string manipulation to higher data structures and interpreters of programming languages. Some of these examples serve as a reference to illustrate definitions and results, others may throw a light on the strong link between specifications and programs, which are executed by applying deduction rules. Thus we have included examples of how to use program trans/ormation methods in specification design.

---

This book presents a unifying approach to semantical concepts and deductive methods used in recursive, equational and logic programming, data type specification and automated theorem-proving. The common background is Horn logic with equality. Although this logic does not cover the full first-order logic, it supplies us with a language that allows "natural" problem specifications, offers several semantical views (functional, relational, inductive, behavioural, etc.) and puts at our disposal a number of more or less special-purpose deductive methods, which can be used as rapid prototyping tools. The Horn clause calculus serves as the interface between the model-theoretic concepts of initial semantics, final semantics and internalized logic on one hand and deductive methods based on resolution, paramodulation, reduction and narrowing on the other hand. This contrasts previous approaches, which equip each semantical concept with its own calculus or, conversely, build a particular semantics upon each deductive method. Here the author starts out from the Horn clause calculus and develops individual concepts, results and procedures in a way that clearly delimits their respective purposes from each other. The unifying approach also brings about new variants or generalizations of known results and admits comparable arguments in soundness and completeness proofs.

---

This book presents a unifying approach to semantical concepts and deductive methods used in recursive, equational and logic programming, data type specification and automated theorem-proving. The common background is Horn logic with equality. Although this logic does not cover the full first-order logic, it supplies us with a language that allows "natural" problem specifications, offers several semantical views (functional, relational, inductive, behavioural, etc.) and puts at our disposal a number of more or less special-purpose deductive methods, which can be used as rapid prototyping tools. The Horn clause calculus serves as the interface between the model-theoretic concepts of initial semantics, final semantics and internalized logic on one hand and deductive methods based on resolution, paramodulation, reduction and narrowing on the other hand. This contrasts previous approaches, which equip each semantical concept with its own calculus or, conversely, build a particular semantics upon each deductive method. Here the author starts out from the Horn clause calculus and develops individual concepts, results and procedures in a way that clearly delimits their respective purposes from each other. The unifying approach also brings about new variants or generalizations of known results and admits comparable arguments in soundness and completeness proofs.
Content:
Front Matter....Pages I-XI
Introduction....Pages 1-5
Basic Notions....Pages 7-13
Sample Specifications....Pages 15-52
Models and Theories....Pages 53-111
Resolution and Paramodulation....Pages 113-137
The Relevance of Constructors....Pages 139-152
Reduction....Pages 153-186
Narrowing....Pages 187-240
Church-Rosser Criteria....Pages 241-305
Back Matter....Pages 307-322

---

This book presents a unifying approach to semantical concepts and deductive methods used in recursive, equational and logic programming, data type specification and automated theorem-proving. The common background is Horn logic with equality. Although this logic does not cover the full first-order logic, it supplies us with a language that allows "natural" problem specifications, offers several semantical views (functional, relational, inductive, behavioural, etc.) and puts at our disposal a number of more or less special-purpose deductive methods, which can be used as rapid prototyping tools. The Horn clause calculus serves as the interface between the model-theoretic concepts of initial semantics, final semantics and internalized logic on one hand and deductive methods based on resolution, paramodulation, reduction and narrowing on the other hand. This contrasts previous approaches, which equip each semantical concept with its own calculus or, conversely, build a particular semantics upon each deductive method. Here the author starts out from the Horn clause calculus and develops individual concepts, results and procedures in a way that clearly delimits their respective purposes from each other. The unifying approach also brings about new variants or generalizations of known results and admits comparable arguments in soundness and completeness proofs.
Content:
Front Matter....Pages I-XI
Introduction....Pages 1-5
Basic Notions....Pages 7-13
Sample Specifications....Pages 15-52
Models and Theories....Pages 53-111
Resolution and Paramodulation....Pages 113-137
The Relevance of Constructors....Pages 139-152
Reduction....Pages 153-186
Narrowing....Pages 187-240
Church-Rosser Criteria....Pages 241-305
Back Matter....Pages 307-322
....