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

Previous Article

Next Article

Contents of this Issue

Other Issues

ELibM Journals

ELibM Home


Pick a mirror



Milenko Mosurovic

Prirodno-matematicki fakultet
81000 Podgorica

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
© 2008 ELibM and FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition