Default Logic: From Theory to Applications

Ilkka Niemelš

A course given at the 11th European Summer School in Logic, Language and Information , Utrecht University, Aug 16-20, 1999.

Course Description

Nonmonotonic reasoning has been one of the most active research areas in knowledge representation and reasoning since the late seventies and Reiter's default logic has turned out to be one of the most successful nonmonotonic logics. Default logic offers a very expressive framework for handling knowledge representation tasks in a compact, robust and flexible way even in the presence of difficult issues like the frame problem and the qualification problem. However, the development of applications based on default logic has not been possible because of the lack of efficient implementations. Recently, the situation has changed by breakthroughs in computational techniques for default reasoning leading to efficient implementations for fragments of Reiter's default logic. For example, the Smodels system, which is an implementation of a subset corresponding to normal logic programs with the stable model semantics, is able to handle realistic size problems (tens of thousands of default rules) with competitive performance. For instance, in planning it has shown comparable and occasionally even better performance than the best domain independent planning systems such as Graphplan.

The objective of the course is to introduce basic default logic and its most important subclasses corresponding to logic programs, explain relevant expressivity and complexity results, present implementation methods behind the computational breakthrough and discuss application methodology for default reasoning. An interesting approach to developing applications for default reasoning is to see default logic as a framework for declarative rule-based constraint programming. This approach is introduced, its relation to standard constraint satisfaction is explained and examples of applications in combinatorial problems, planning, and product configuration are discussed. A distinguishing feature of the course is the availability of an efficient implementation, the Smodels system, which makes it possible to obtain hands-on experience in using default reasoning techniques.

Slides for the lectures: