Publications de l'Institut Mathématique, Nouvelle Série
Vol. 82(96), pp. 25–35 (2007)
DISJUNCTION IN MODAL DESCRIPTION LOGICS
Milenko MosurovicPrirodno-matematicki fakultet
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