Restricted default theories: expressive power and outlier detection tasks

We study the tractability frontier of outlier detection problems, by analyzing it with respect to (i) the considered outlier detection problem, (ii) the reference default logic fragment, and (iii) the adopted notion of outlier. As for point (i), we shall consider three problems of increasing complexity, called Outlier-Witness Recognition, Outlier Recognition and Outlier Existence, respectively. As for point (ii), as we look for conditions under which outlier detection can be done efficiently, attention will be limited to subsets of Disjunction-free propositional default theories. As for point (iii), we shall refer to both the notion of outlier introduced in [3] and a new and more restrictive one, called strong outlier. We also present a polynomial time algorithm for enumerating all strong outliers of bounded size in a quasi-acyclic normal unary default theory. Some of our tractability results rely on the Incremental Lemma that provides conditions for a default logic fragment to have a monotonic behavior. Finally, in order to show that the simple fragments of DL we deal with are still rich enough to solve interesting problems and, therefore, that the tractability results that we prove are interesting not merely on the theoretical side, insights into the expressive capabilities of these fragments are provided, by showing that normal unary theories express all NL queries, hereby indirectly answering a question raised by Kautz and Selman [16].