Artificial Intelligence Techniques in Prolog
- 1st Edition - December 1, 1993
- Imprint: Morgan Kaufmann
- Author: Yoav Shoham
- Language: English
- eBook ISBN:9 7 8 - 1 - 4 8 3 2 - 1 4 4 9 - 8
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… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteArtificial 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.
Preface
Acknowledgements
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
- Edition: 1
- Published: December 1, 1993
- Imprint: Morgan Kaufmann
- Language: English
- eBook ISBN: 9781483214498
Read Artificial Intelligence Techniques in Prolog on ScienceDirect