  In default theories, outliers denote sets of literals featuring unexpected
properties. In previous papers, we have defined outliers in default logics and
investigated their formal properties. Specifically, we have looked into the
computational complexity of outlier detection problems and proved that while
they are generally intractable, interesting tractable cases can be singled out.
Following those results, we study here the tractability frontier in 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 of [ABP08] and
a new and more restrictive one, called strong outlier. After complexity
results, we present a polynomial time algorithm for enumerating all strong
outliers of bounded size in an quasi-acyclic normal unary default theory. Some
of our tractability results rely on the Incremental Lemma that provides
conditions for a deafult 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, the tractability results
that we prove are interesting not only on the mere 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.
