Re: Intersection of properties?

On 3 Aug 2008, at 21:25, Bijan Parsia wrote:

>
> On Aug 3, 2008, at 8:55 PM, Michael Schneider wrote:
>
>> Two questions for my interest:
>>
>> Bijan Parsia wrote:
>>
>>> On Aug 3, 2008, at 7:58 PM, Jeff Thompson wrote:
>>
>>>> And yet, the argument against
>>>> adding more expressiveness to OWL 2 (still decidable) is the fear
>>>> that not enough people will implement it and so that "OWL 2  
>>>> compliant"
>>>> won't mean much.
>>>
>>> What? The argument against boolean role boxes, in general, is that
>>> it's relatively hard to do and there's been relatively little demand
>>> for it.
>>
>> Question 1: Is sROIQ + role intersection known to be decidable? 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?
>
> The navigator is, indeed, lagging. My best guess is that it is  
> unknown. Uli?

I would *guess* it's still decidable, and I think Glimm&Kazakov have a  
KR2008 paper that tells us more about role conjunction in SHIF, SHOIN,  
etc...namely, that it increases computational complexity (which might  
never be "felt" in practice, but which might also be an indicator that  
we might need *novel* reasoning techniques for which we need to gain  
some experience and develop optimisations first):

 From Glimm&Kazakov 2008, Role Conjunctions in Expressive Description  
Logics Birte Glimm, Yevgeny Kazakov Technical Report, 2008. :

We show that adding role conjunctions to the prominent DLs
SHIF and SHOIN causes a jump in the computational complexity
of the standard reasoning tasks from ExpTime to 2ExpTime already for
S HI and from NExpTime to N2ExpTime for S HOI F . We further show
that this increase in complexity is due to a subtle interaction between
inverse roles, role hierarchies, and role transitivity in the presence  
of role
conjunctions and that for the DL SHQ a jump in the computational
complexity cannot be observed.

Cheers, Uli

>
>
>>> 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.)
>
> Indeed. ALBO subsumes the 2 variable fragment (L2). So, I guess the  
> only question is how chains (i.e., transitivity) and number  
> restrictions interact with the rest. C2 is decidable (obviously), so  
> maybe it's all down to chains. Uli (again)?
>
> Cheers,
> Bijan.
>