The book was published in early 2003. Please see for supplementary materials for the book.

The table of contents as of 7/31/01 (1MB)

Smodels and dlv code of the examples in the book (not properly commented yet)

Funding acknowledgement: The author was supported by ASU Dept of Computer Science through a start-up package, by NSF through grants IRI-9501577 and 0070463 and by NASA through grant NCC2-1232.


Representing knowledge and reasoning with it are important components of an intelligent system, and are two important facets of Artificial Intelligence. Another important expectation from intelligent systems is their ability to accept high level requests -- as opposed to detailed step-by-step instructions, and to use their knowledge and reasoning ability to figure out the detailed steps that need to be taken. To have this ability intelligent systems must have a declarative interface whose input language must be based on logic.

Thus the author considers the all-round development of a suitable declarative knowledge representation language to be a fundamental component of knowledge based intelligence, perhaps similar to the role of the language of Calculus to mathematics, and physics. Taking the Calculus analogy further, it is important that a large support structure is developed around the language, similar to the integration and derivation formulas and the various theorems around Calculus.

Although several languages have been proposed for knowledge representation, the language of AnsProlog* -- logic programming with the answer set semantics, stands out in terms of the size and variety of the support structure developed around it. The support structure includes both implementations and use of the implementations in developing applications, and theoretical results for both analyzing and step-by-step building of theories (or programs) in this language. The support structure and the desirable properties of the language are also a testimony to the appropriateness of the language for knowledge representation, reasoning and declarative problem solving.

This book is about AnsProlog* and compiles the various results obtained over the years about AnsProlog*. This book is expected to be useful to researchers in logic programming, declarative programming, artificial intelligence, knowledge representation, and autonomous agents; to knowledge engineers who would like to create and use large knowledge bases; to software practitioners who would like to use declarative programming for fast prototyping, and for developing critical programs that must be correct with respect a formal specification; to programmers of autonomous agents who would like to build intelligent components such as planners, schedulers, and diagnosis and repair systems; and to students and teachers using it as a text book in undergraduate and graduate classes.

The distinguishing features of this book are: (i) It uses answer set semantics of logic programs. (ii) A big part of this book is about declarative programming and knowledge representation methodology. It presents several small and big example modules, and presents the theory that describes when modules can be combined, when a module is consistent, how to incorporate an observation, etc. (iii) Because it uses answer set semantics which allows multiple `models' of a theory, it is able to go beyond reasoning to declarative problem solving. Thus it includes encoding of applications such as planning, diagnosis, explanation generation, scheduling, combinatorial auctions, abductive reasoning, etc. Most of these applications are related to encoding problems that are {\bf NP}-complete or beyond. The book also explores the well-founded semantics. Since the well-founded semantics is sound with respect to answer set semantics and is easier to compute, in this book it is treated as an approximation to answer-set semantics. (iv) The book discusses complexity and expressiveness issues and identifies subsets belonging to different complexity and expressiveness classes. (v) It presents algorithms to compute answer sets. Some of the algorithms it discusses use heuristics and other intelligent search ideas. (vi) Most of the programs discussed in the book can be run. It uses the smodels and the dlv interpreter for this and is supplemented by a web site containing a large subset of the example programs as smodels or dlv code. We now give a brief description of the various chapters of the book.