The past decade has witnessed an explosion of interest in nonmonotonic reasoning from scientists in such fields as artificial intelligence, linguistics, and philosophy, creating a strong need for a comprehensive introduction to nonmonotonic reasoning. This concise book gives a broad overview of the state of the art of research in this rapidly growing field. In trying to reach both beginners and specialists in nonmonotonic reasoning research, the author presents his own new proposals and results, in addition to a broad overview of important topics in this area.
The book has 10 chapters. Chapter 1 is a brief introduction and chapter 10 is a discussion of achievements and future directions. Chapters 2 through 9 can be divided into two parts. The first part, chapters 2 through 6, presents the most important existing nonmonotonic logics. The author also describes modifications of or generalizations to the existing approaches. The second part, chapters 7 through 9, focuses on computational aspects of deduction in the various nonmonotonic logics.
Chapter 2, “Modal Approaches,” discusses the nonmonotonic logic of McDermott and Doyle as well as Moore’s autoepistemic logic. Hierarchic autoepistemic logic is also described.
Chapter 3 covers default logics, which are based on nonmonotonic inference rules (defaults) in addition to the ordinary modus ponens inference rule in first-order logic. Reiter’s default logic is presented. The author also proposes some modifications and describes his cumulative default logic. Chapter 4, “Circumscription,” discusses McCarthy’s predicate circumscription and prioritized circumscription.
Approaches based on preferred subtheories are presented in chapter 5. This approach starts with a set of inconsistent formulas and selects preferred maximal consistent subsets of it. The author presents Poole’s theory of default reasoning based on preferred subtheories. Extensions to Poole’s work by the author are also given. Chapter 6 addresses “Conditional Logics.” This approach introduces a binary connective to express default implication. Delgrande’s conditional logic for default reasoning is discussed.
The second part of the book (chapters 7 through 9) addresses the computational aspects of inferencing in the above nonmonotonic logics. The main problem, which is shared by all the nonmonotonic logics, is that they are computationally intractable. In fact, with few exceptions, they are not even semi-decidable. Thus, it is important to investigate ways to integrate theoretical soundness and computational tractability, so that we can effectively handle at least some part of the nonmonotonic logics. The author discusses three possible ways to do this:
Identify interesting subsets of the logics for which efficient proof procedures exist.
Take existing implemented nonmonotonic reasoning systems and try to formalize them in the known nonmonotonic logics.
Compute approximations of the theoretically required results.
All three approaches are discussed in chapters 7 through 9. Chapter 7 presents various proof procedures for circumscription, default logic, autoepistemic logic, and so on. Chapter 8 discusses inheritance systems and their formalizations, including Touretzky’s work and a method based on DL, logic of frames with exceptions. This corresponds to the second approach. Chapter 9 presents nonmonotonic rule-based systems, in particular truth-maintenance systems and dependency-directed backtracking.
Readers should have a basic knowledge of first-order logic. With this preparation, they will find that the book gives a quick, broad introduction to nonmonotonic reasoning. The length of the book is suitable; the author uses the space economically. It can be used as a reference book or a tutorial for a graduate course on nonmonotonic reasoning, supplemented by the original papers. Specialists in nonmonotonic reasoning can also benefit from reading the chapters discussing the author’s proposals. Since the proofs and more detailed illustrations of the theorems are not included in the book, it is not suitable as a textbook.
