Artificial Intelligence Techniques in Prolog - 1st Edition - ISBN: 9781483214498

Artificial Intelligence Techniques in Prolog

1st Edition

Authors: Yoav Shoham
eBook ISBN: 9781483214498
Imprint: Morgan Kaufmann
Published Date: 12th May 2014
Page Count: 348
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.


Artificial Intelligence Techniques in Prolog introduces the reader to the use of well-established algorithmic techniques in the field of artificial intelligence (AI), with Prolog as the implementation language. The techniques considered cover general areas such as search, rule-based systems, and truth maintenance, as well as constraint satisfaction and uncertainty management. Specific application domains such as temporal reasoning, machine learning, and natural language are also discussed.

Comprised of 10 chapters, this book begins with an overview of Prolog, paying particular attention to Prolog terms and rules (and Prolog facts as special cases); unification; the and-or computation tree induced by a Prolog program and a query; the depth-first, left-to-right traversal of that tree by the standard Prolog interpreter; and built-in predicates such as unification and equality. Subsequent chapters deal with search and representation of graphs in Prolog; backward-chaining methods; truth maintenance systems; and constraint satisfaction. Reasoning with uncertainty, planning and temporal reasoning, and machine learning are also tackled. The book concludes with an assessment of natural language processing and some of the linguistic notions that are easily encoded in Prolog.

This monograph will be of interest to both students and practitioners in the fields of AI and computer science.

Table of Contents



Software Availability

1 On Prolog

1.1 A Checklist

1.2 Additional Prolog Material

1.2.1 Standard Lists and 'and' Lists

1.2.2 'All-Solutions' Predicates

1.2.3 Indexing

1.2.4 Last-Call Optimization

1.2.5 Difference Lists and 'Holes'

1.2.6 Static and Dynamic Predicates

1.2.7 Bitwise Operations

1.2.8 Database References

1.3 Utility Predicates

2 Search

2.1 Review of Basic Graph-Theoretic Terminology

2.2 Representing Graphs in Prolog

2.2.1 Representing Graphs

2.2.2 Representing Trees

2.2.3 Representing and-or Trees

2.3 Review of Graph Search Techniques

2.4 Depth-First Search

2.5 Breadth-First Search

2.6 Iterative Deepening

2.7 Best-First Search

2.7.1 The General Best-First Algorithm

2.7.2 The A* Algorithm

2.8 Game-Tree Search

2.8.1 Minimax Search

2.8.2 α-β Search

2.9 Further Reading

2.10 Exercises

3 Backward-Chaining Methods

3.1 The Basic Meta-Interpreter

3.2 A Full Standard Meta-Interpreter

3.3 A Modified Depth-First Meta-Interpreter

3.4 Toward an Expert-System Shell

3.4.1 An Explanatory Meta-Interpreter

3.4.2 An Interpreter with a Query Mechanism

3.5 Partial Evaluation

3.6 A Breadth-First Meta-Interpreter

3.7 A Best-First Meta-Interpreter

3.8 Further Reading

3.9 Exercises

4 Other Rule-Based Methods

4.1 Forward Chaining

4.1.1 Representing Positive Forward-Chaining Rules

4.1.2 Forward Chaining with Positive Rules, Unoptimized

4.1.3 Optimizing the Implementation

4.1.4 Representing General Forward-Chaining Rules

4.1.5 Forward Chaining with Negative Conditions

4.1.6 Termination Conditions for Forward Chaining

4.1.7 Variables in Forward-Chaining Rules

4.2 Production Systems

4.2.1 The General Structure of a Production System

4.2.2 Implementing a Generic Production System

4.2.3 Determining the Conflict Set

4.2.4 Resolving the Conflict Set

4.2.5 Firing a Production Rule

4.3 Further Reading

4.4 Exercises

5 Truth Maintenance Systems

5.1 Reason Maintenance

5.1.1 Justifications and Premises

5.1.2 Operations on RMSs

5.1.3 An Inefficient Prolog Implementation

5.1.4 Optimizing the Implementation

5.2 Consistency Maintenance

5.3 Assumption-Based Truth Maintenance

5.3.1 The Structure of an ATMS

5.3.2 Operations on an ATMS

5.3.3 An Implementation of an ATMS

5.4 Further Reading

5.5 Exercises

6 Constraint Satisfaction

6.1 Precise Definition of CSP

6.2 Overview of Constraint Satisfaction Techniques

6.3 Consistency Enforcing

6.4 Consistency Enforcing in Temporal Reasoning

6.5 Further Reading

6.6 Exercises

7 Reasoning with Uncertainty

7.1 Representing Uncertainty in the Database

7.2 A General Meta-Interpreter with Uncertainty

7.3 Informal Heuristics

7.4 Certainty Factors in MYCIN

7.5 A Review of Probability Theory

7.6 Bayesian Networks

7.7 Further Reading

7.8 Exercises

8 Planning and Temporal Reasoning

8.1 Basic Notions

8.1.1 Plan and Action Libraries

8.1.2 The Blocks World

8.1.3 Planning Problems

8.2 Linear Planning

8.2.1 Strips

8.2.2 Goal Protection and Goal Regression

8.3 Nonlinear Planning

8.4 Time Map Management

8.4.1 The Basic Time Map Manager

8.4.2 Abductive Queries

8.4.3 Causal Time Maps

8.5 Further Reading

8.6 Exercises

9 Machine Learning

9.1 Inductive Inference

9.1.1 Concept Hierarchies

9.1.2 Prolog Representation of Concept Hierarchies

9.1.3 Inductive Inference Algorithms

9.2 Induction of Decision Trees (ID3)

9.3 Explanation-Based Learning

9.3.1 Generalizing Correct Reasoning

9.3.2 Learning from Failed Reasoning

9.4 Further Reading

9.5 Exercises

10 Natural Language

10.1 Syntax

10.1.1 Context-Free Grammars

10.1.2 Definite Clause Grammars (DCGs)

10.1.3 Parse Trees

10.1.4 Syntactic Extensions

10.2 Semantics

10.2.1 Semantic Representation

10.2.2 Compositionality Principle

10.2.3 Quantification

10.2.4 Tensed Verbs

10.3 Further Reading


No. of pages:
© Morgan Kaufmann 1994
Morgan Kaufmann
eBook ISBN:

About the Author

Yoav Shoham

Ratings and Reviews