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

EMIS Home

Pick a mirror

 		 

DISJUNCTION IN MODAL DESCRIPTION LOGICS

Milenko Mosurovic

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