Skip to main content
SpringerLink
Log in
Book cover

Instantiation Theory

On the Foundations of Automated Deduction

  • Book
  • © 1991

Overview

Authors:
  1. James G. Williams
    View author publications

    You can also search for this author in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 518)

Part of the book sub series: Lecture Notes in Artificial Intelligence (LNAI)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (10 chapters)

  1. Front Matter

    Download chapter PDF

  2. Introduction

    Pages 1-3

  3. Background

    Pages 4-10

  4. General approaches to instantiation

    Pages 11-22

  5. Classification properties

    Pages 23-36

  6. Homomorphisms

    Pages 37-48

  7. Construct bases

    Pages 49-60

  8. Unification - an algorithm and its soundness

    Pages 61-80

  9. Term-implementation and completeness

    Pages 81-96

  10. Implementation and computational complexity

    Pages 97-120

  11. Related issues not addressed

    Pages 121-121

  12. Back Matter

    Download chapter PDF
Back to top

Keywords

About this book

Instantiation Theory presents a new, general unification algorithm that is of immediate use in building theorem provers and logic programming systems. Instantiation theory is the study of instantiation in an abstract context that is applicable to most commonly studied logical formalisms. The volume begins with a survey of general approaches to the study of instantiation, as found in tree systems, order-sorted algebras, algebraic theories, composita, and instantiation systems. A classification of instantiation systems is given, based on properties of substitutions, degree of type strictness, and well-foundedness of terms. Equational theories and the use of typed variables are studied in terms of quotient homomorphisms and embeddings, respectively. Every instantiation system is a quotient system of a subsystem of first-order term instantiation. The general unification algorithm is developed as an application of the basic theory. Its soundness is rigorously proved, and its completeness and efficiency are verfied for certain classes of instantiation systems. Appropriate applications of the algorithm include unification of first-order terms, order-sorted terms, and first-order formulas modulo alpha-conversion, as well as equational unification using simple congruences.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation