Publications de l'Institut Mathématique, Nouvelle Série Vol. 82(96), pp. 25–35 (2007) 

DISJUNCTION IN MODAL DESCRIPTION LOGICSMilenko MosurovicPrirodnomatematicki fakultet81000 Podgorica Montenegro Abstract: 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. Classification (MSC2000): 03B70; 68T27; 68Q17 Full text of the article: (for faster download, first choose a mirror)
Electronic fulltext finalized on: 20 Feb 2008. This page was last modified: 26 Feb 2008.
© 2008 Mathematical Institute of the Serbian Academy of Science and Arts
