Semantics and expressiveness of disjunctive ordered logic

The paper proposes a knowledge representation language which extends logic programming with disjunction, inheritance, true negation and modularization . The resulting language is called Disjunctive Ordered Logic (DOL for short ). A model-theoretic semantics for DOL is given, and it is shown to extend the stable model semantics of disjunctive logic programs. A number of examp les show the suitability of DOL for knowledge representation and commonsens e reasoning. Among other things, the proposed language appears to be a powe rful tool for the description of diagnostic processes which are based on st epwise refinements. The complexity and the expressiveness of the language a re carefully analyzed. The analysis pays particular attention to the relati ve power and complexity of inheritance, negation and disjunction. An intere sting result in this course concerns the role played by inheritance. Indeed , our results show that inheritance does not increase at all the complexity of any fragment of the language, while it does increase the expressive pow er of some DOL fragments.