Disjunction in Modal Description Logics

Milenko Mosurović

We investigate the complexity of satisfaction problems in modal description logics without disjunction between formulae. It is shown that simulation of disjunction in the class of all models of these logics is possible, so that the complexity remains same no matter the logics is with or without disjunction of formulae. However, the omission of disjunction, in the class of the models based on the universal relation, ``turns down" the complexity of satisfaction problem i.e., if P $\neq$ NP, it is not possible to simulate disjunction.