In [De 95] complexity results for various DLs are obtained by sophisticated polynomial reduction to a propositional dynamic logic. The author establishes many complexity results, one of which is of special interest for our purposes.
knowledge
bases (TBox and ABox) are
-complete.
The DL
studied by the author is a strict extension of
;
TBoxes in his thesis correspond to what we call
in this
paper. Unary coding of numbers is assumed throughout his thesis. Although a
unique name assumption is made, it is not inherent to the utilised reduction
since is explicitly enforced. It is thus possible to eliminate the
propositions that require a unique interpretation of individuals from the
reduction. Hence, together with Lemma 4.2, we get the
following corollary.
-
is
-complete if unary coding of
number is assumed.
Together with Theorem 4.5, this solves the open problem
concerning the lower bound for the complexity of
with cardinality
restrictions; moreover, it shows that the
-algorithm presented in
[BBH96] is not optimal with respect to worst case complexity.
-
is
-complete, if unary coding of numbers
in cardinality and number restrictions is used.