Knowledge representation, reasoning and declarative problem solving. (English) Zbl 1056.68139

Cambridge: Cambridge University Press (ISBN 0-521-81802-8/hbk). xiv, 530 p. (2003).
Theoretical investigation of principles of Answer Set Programming (ASP) and applications of ASP to knowledge representation and problem solving are presented in the book. The language for knowledge representation AnsProlog* is proposed and used. ASP is based on answer set semantics of logic programs; queries are answered with respect to answer sets of programs.
Chapter 1 motivates importance of declarative programming. AnsProlog* is compared with other declarative languages and also with Prolog. Syntax and semantics of various subclasses of AnsProlog* are presented. Some small AnsProlog* programs (problem solving or knowledge representation modules) are presented in Chapter 2.
Fundamental theoretical results that are useful in analyzing and step-by-step building of AnsProlog* programs are introduced in Chapter 3. Such properties as categoricity, coherence, computability, filter-abductibility, language independence, language tolerance, strong equivalence, compilability to a first-order theory are studied. Several important sub-classes of AnsProlog* are defined. The notion of splitting is introduced and it is shown how the notion can be used in step-by-step computation of answer sets.
Chapter 4 is devoted to declarative problem solving and reasoning with AnsProlog*. Focus is on program development. After discussing examples from domains such as constraint satisfaction, automated reasoning, combinatorial graph problems, a general methodology of reasoning with prioritized defaults is presented. Reasoning about actions and planning is considered in the next chapter. Applications to observation assimilation and explanation, and to diagnosis are discussed, too.
Complexity, expressiveness, modularity of AnsProlog* and its relations to other nonmonotonic formalisms is studied in Chapter 6. Answer set computing algorithms are presented, analyzed and compared in Chapter 7. The attention is devoted to an algorithm that uses branch and bound after computing the well-founded model, to the assume-and-reduce algorithm, to the smodels algorithm and to the dlv algorithm.
In chapter 8 it is explained how to program using smodels and dlv systems. Features of these systems that extend AnsProlog* are discussed and some programs are presented. It is described when a Prolog interpreter can be used in answering questions to AnsProlog* programs and under what conditions the Prolog interpreter is sound and complete with respect to AnsProlog*. Applications of smodels and dlv in domains such as combinatorial auctions, planning, scheduling, specification and verification of active databases are presented.
Several extensions to AnsProlog* are discussed in Chapter 9. The following features are allowed in the extensions: not in heads of rules, nested expressions, epistemic operators, abductive reasoning, set constructs, specification of priorities between rules.
I conclude with the remark that the appearance of an extensive book with such a deep theoretical content and with analyses, methods and examples useful for practical applications is admirable after the very short history of ASP.


68T30 Knowledge representation
68N17 Logic programming
68T27 Logic in artificial intelligence
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
Full Text: DOI