Affiliations: DEIS, University of Calabria, 87030 Rende, Italy and ISI-CNR, 87030 Rende, Italy | Information System Department, Technical University of Vienna, A-1040 Wien, Paniglgasse 16, Austria and ISI-CNR, 87030 Rende, Italy | DEIS, University of Calabria, 87030 Rende, Italy
Note: [] Please address correspondence to Francesco Scarcello, DEIS, Universita' della Calabria, 87030 Rende, Italy. Email addresses: bucca@si.deis.unical.it; frank@si.deis.unical.it; leone@vexpert.dbai.tuwien.ac.at
Abstract: Ordered Logic ($\mathcal{OL}$) is an elegant, yet powerful extension of logic programming with the object-oriented notions of modules, inheritance and exceptions. The capability to naturally express several forms of nonmonotonic reasoning is a major feature of $\mathcal{OL}$ and has recently candidated this language as a powerful tool for knowledge representation and reasoning. After an overview of $\mathcal{OL}$, the paper analyzes the expressive power of the language. The expressibility of $\mathcal{OL}$ under both brave and cautious inference modalities is formally determined by applying Fagin's theorem. The results show that under the cautious inference modality $\mathcal{OL}$ captures the complexity class co-NP; while under the brave inference modality, $\mathcal{OL}$ captures the complexity class NP.
