Re: Intersection of properties?

>> Question 1: Is sROIQ + role intersection known to be decidable?
>
> Yes.

I am not sure whether the lower case s in sROIQ means something like a
restriction to simple roles in role conjunctions, but just to clarify:
in the papers below it is shown that if you do not use transitive
properties or properties that have a transitive sub-property, then
adding role conjunctions does not increase the complexity of the
standard reasoning tasks, whereas our paper shows that without
restrictions on the roles used in role conjunctions you can have an
exponential blow-up (for OWL Lite and DL) and decidability is not even
clear for OWL DL and OWL2.
For number restrictions, a similar restrictions is placed on the
properties because for number restrictions it is known that without
the restriction the reasoning tasks becomes undecidable. If one would
want to extend OWL with conjunctions over properties (or even full
Boolean operators), either a restriction to simple roles can be used
or decidability for these DLs should be studied before extending the
standard and even then, one has to decide whether an exponential jump
in the complexity is acceptable.
Birte

> Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler. Cheap Boolean Role
> Constructors for Description Logics. To appear in Proc. JELIA2008.
> <http://korrekt.org/page/DL_Role_Constructors>
> <http://www.aifb.uni-karlsruhe.de/WBS/sru/TR-RKH-bool-role.pdf>
>
> Also, EL++ remains tractable with role conjunctions. Same reference.
>
> Pascal.
>
>> The
>> Complexity simulator [1] only tells me that concept satisfiability is
>> NExpTime hard, but there's no explicit statement that this language is
>> decidable. (For sROIQ, however, there exists such an explicit statement.)
>> But maybe this statement has just been forgotten, or the entry is not up
>> to
>> date with the literature. So what's the state here?
>>>
>>> ALBO is *very* expressive but, you know, doesn't have
>>> cardinality restrictions.
>>
>> Question 2: I guess that the "B" stands for "[B]oolean role box", and
>> probably subsumes a few more language features, too, right? (I don't find
>> "B" mentioned in the complexity simulator.)
>>
>> Thanks in advance,
>> Michael
>>
>> [1] <http://www.cs.man.ac.uk/~ezolin/dl/>
>>
>> --
>> Dipl.-Inform. Michael Schneider
>> FZI Forschungszentrum Informatik Karlsruhe
>> Abtl. Information Process Engineering (IPE)
>> Tel  : +49-721-9654-726
>> Fax  : +49-721-9654-727
>> Email: Michael.Schneider@fzi.de
>> Web  : http://www.fzi.de/ipe/eng/mitarbeiter.php?id=555
>>
>> FZI Forschungszentrum Informatik an der Universität Karlsruhe
>> Haid-und-Neu-Str. 10-14, D-76131 Karlsruhe
>> Tel.: +49-721-9654-0, Fax: +49-721-9654-959
>> Stiftung des bürgerlichen Rechts
>> Az: 14-0563.1 Regierungspräsidium Karlsruhe
>> Vorstand: Rüdiger Dillmann, Michael Flor, Jivka Ovtcharova, Rudi Studer
>> Vorsitzender des Kuratoriums: Ministerialdirigent Günther Leßnerkraus
>>
>
> --
> PD Dr. Pascal Hitzler
> Institute AIFB, University of Karlsruhe (TH), 76128 Karlsruhe
> email: hitzler@aifb.uni-karlsruhe.de    fax: +49 721 608 6580
> web:   http://www.pascal-hitzler.de   phone: +49 721 608 4751
> Springer Lehrbuch:      http://www.semantic-web-grundlagen.de
>
>
>

Received on Monday, 4 August 2008 13:29:22 UTC