Knowledge base vivification by model-preference default inference

A class of default reasoning systems based on the notion of "model-preference" have recently been proposed by Selman and Kautz. These systems are similar in spirit to Shoham's "preferential" logics; however, unlike the latter, they are not general-purpose reasoning tools, but are specially designed for the task of knowledge base vivification, i.e. the generation of a complete, vivid knowledge from an incomplete one and a set of default implications. Vivid knowledge bases are "pictorial-like" representations of the domain of discourse, and reasoning on them is provably efficient. Research on model-preference systems attempts to define systems that be at the same time expressively powerful (thus allowing the representation of rich forms of default and categorial knowledge), computationally tractable (thus allowing vivid knowledge bases to be generated in polynomial time) and semantically well-funded. In this paper we review the current state of research on MPD systems, and discuss some open problems relating either to their epistemological adequacy or to their computational complexity.