Knowledge Representation, Reasoning and Declarative Problem Solving

by Chitta Baral

• ISBN13: 9780521818025
• ISBN10: 0521818028
• Format: Hardcover
• Copyright: 2003-02-24
• Publisher: Cambridge University Press

Summary

Knowledge management and knowledge-based intelligence are areas of importance in today’s economy and society, and to exploit them fully and efficiently it is necessary both to represent and reason about knowledge via a declarative interface whose input language is based on logic. In this book, Chitta Baral shows exactly how to go about doing that: how to write programs that behave intelligently by giving them the ability to express knowledge and reason about it. He presents a language, AnsProlog, for both knowledge representation and reasoning, and declarative problem solving. Many of the results here have never appeared before in book form, and they have been organised here into a form that will appeal to practising and would-be knowledge engineers wishing to learn more about the subject, either in courses or through self-teaching. A comprehensive bibliography rounds off the book.

Table of Contents

Preface	ix
1 Declarative programming in AnsProlog*: introduction and preliminaries	1	(45)
1.1 Motivation: Why AnsProlog*?	3	(5)
1.2 Answer set frameworks and programs	8	(8)
1.3 Semantics of AnsProlog* programs	16	(24)
1.4 Database queries and AnsProlog* functions	40	(4)
1.5 Notes and references	44	(2)
2 Simple modules for declarative programming with answer sets	46	(37)
2.1 Declarative problem solving modules	47	(26)
2.2 Knowledge representation and reasoning modules	73	(8)
2.3 Notes and references	81	(2)
3 Principles and properties of declarative programming with answer sets	83	(87)
3.1 Basic notions and basic properties	84	(9)
3.2 Some AnsProlog* sub-classes and their basic properties	93	(15)
3.3 Restricted monotonicity and signed AnsProlog* programs	108	(5)
3.4 Analyzing AnsProlog* programs using `splitting'	113	(7)
3.5 Language independence and language tolerance	120	(6)
3.6 Interpolating an AnsProlog program	126	(11)
3.7 Building and refining programs from components: functional specifications and realization theorems	137	(7)
3.8 Filter-abducible AnsProlog-' or programs	144	(10)
3.9 Equivalence of programs and semantics preserving transformations	154	(14)
3.10 Notes and references	168	(2)
4 Declarative problem solving and reasoning in AnsProlog*	170	(29)
4.1 Three well-known problem solving tasks	170	(13)
4.2 Constraint satisfaction problems (CSPs)	183	(3)
4.3 Dynamic constraint satisfaction problems (DCSPs)	186	(2)
4.4 Combinatorial graph problems	188	(4)
4.5 Prioritized defaults and inheritance hierarchies	192	(5)
4.6 Notes and references	197	(2)
5 Reasoning about actions and planning in AnsProlog*	199	(79)
5.1 Reasoning in the action description language A	199	(30)
5.2 Reasoning about actions and plan verification in richer domains	229	(15)
5.3 Answer set planning examples in extensions of A and STRIPS	244	(17)
5.4 Approximate planning when initial state is incomplete	261	(1)
5.5 Planning with procedural constraints	262	(7)
5.6 Explaining observations through action occurrences and application to diagnosis	269	(5)
5.7 Case study: Planning and plan correctness in a space shuttle reaction control system	274	(3)
5.8 Notes and references	277	(1)
6 Complexity, expressiveness, and other properties of AnsProlog* programs	278	(67)
6.1 Complexity and expressiveness	278	(10)
6.2 Complexity of AnsDatalog* sub-classes	288	(13)
6.3 Expressiveness of AnsDatalog* sub-classes	301	(3)
6.4 Complexity and expressiveness of AnsProlog* sub-classes	304	(7)
6.5 Compact representation and compilability of AnsProlog	311	(2)
6.6 Relationship with other knowledge representation formalisms	313	(28)
6.7 Notes and references	341	(4)
7 Answer set computing algorithms	345	(37)
7.1 Branch and bound with WFS: wfs-bb	346	(12)
7.2 The assume-and-reduce algorithm of SLG	358	(5)
7.3 The smodels algorithm	363	(9)
7.4 The dlv algorithm	372	(7)
7.5 Notes and references	379	(3)
8 Query answering and answer set computing systems	382	(76)
8.1 Smodels	382	(21)
8.2 The dlv system	403	(9)
8.3 Applications of answer set computing systems	412	(28)
8.4 Pure PROLOG	440	(16)
8.5 Notes and references	456	(2)
9 Further extensions of and alternatives to AnsProlog*	458	(36)
9.1 AnsProlognot, or,-. L: allowing not in the head	458	(3)
9.2 AnsProlog{not, or ,,,L1*: allowing nested expressions	461	(5)
9.3 AnsProlog-, or. x,M: allowing knowledge and belief operators	466	(4)
9.4 Abductive reasoning with AnsProlog: AnsPrologand	470	(1)
9.5 Domain closure and the universal query problem	471	(4)
9.6 AnsProlog,,: adding set constructs to AnsProlog	475	(2)
9.7 AnsProlog-, programs: AnsProlog, programs with ordering	477	(5)
9.8 Well-founded semantics of programs with AnsProlog syntax	482	(8)
9.9 Well-founded semantics of programs with AnsProlog, syntax	490	(2)
9.10 Notes and references	492	(2)
Appendix A: Ordinals, lattices, and fixpoint theory	494	(2)
Appendix B: Turing machines	496	(2)
Bibliography	498	(21)
Index of notation	519	(3)
Index of terms	522