W3C home > Mailing lists > Public > public-owl-dev@w3.org > April to June 2010

Re: Implementations of LCS for OWL

From: Chris Mungall <cjm@berkeleybop.org>
Date: Thu, 29 Apr 2010 15:00:02 -0700
Cc: Owl Dev <public-owl-dev@w3.org>, sonic@tcs.inf.tu-dresden.de
Message-Id: <07584A2D-6CEE-4982-9871-98799C629917@berkeleybop.org>
To: Alan Rector <rector@cs.man.ac.uk>

On Apr 29, 2010, at 4:08 AM, Alan Rector wrote:

> Chris
>
> Can you define your use case a bit more clearly?

I'm after an implementation of a function:

	lcs(C,D) -> A

where C, D and A are either named classes or class expressions, and A  
subsumes both C and D, and there is no A' such that A'\=A and A  
subsumes both C and D, against some background TBox employing some  
subset of OWL2 constructs and axioms (e.g. EL)

or some approximation thereof (open to heuristic approaches)

> Are you trying to find the simplest expression for a defined class  
> that would be guaranteed to subsume both C and D (excluding simply C  
> or D)?
> If so is the interest in finding the subsumer or in the structure of  
> the expressions in the definition
>
> Are you intrested only in named classes?
>
> e.g. C=B & r some Q
>       D=B & r some S
>
> A = B & r some (Q or S)
>
> or do you care about the named subsumers of Q and S.
>
> (I won't have a solution, but I am curious as to what the problem is?)
>
> Or there's the least common named subsumer in the inferred  
> classification lattice
> using lattice theoretical tools, but I presume that is not what you  
> are asking or
> you wouldn't be asking it.

Correct, it would be a solved problem if the result was drawn only  
from the set of named classes.

> Regards
>
> Alan
>
> On 28 Apr 2010, at 04:18, Chris Mungall wrote:
>
>> I'm looking for efficient implementations of the LCS (least common  
>> subsumer) function for OWL. The function take two classes or class  
>> expressions C, D and return the minimal class or class expression  
>> that subsumes both. Obviously this excludes UnionOf constructs used  
>> in the results. Intersection and existential restrictions would be  
>> fine.
>>
>> I see there's a vast literature on this going back to the earliest  
>> days of DL systems, but surprisingly little in the way of  
>> implementations.
>>
>> The only implementation I'm aware of is SONIC:
>>
>> 	http://wwwtcs.inf.tu-dresden.de/~sonic/
>>
>> But this has two drawbacks from my perspective:
>>
>> * It's not open source, and requires non-open source tools
>> * It looks like it's not maintained (the installation instructions  
>> say that OilEd is required)
>>
>> Ideally the implementation would be open source and well-integrated  
>> with current tools (e.g. works with the OWLAPI and/or OWLlink). I'd  
>> be willing to work a little on the plumbing, but not for closed  
>> source tools.
>>
>>
>>
>
> -----------------------
> Alan Rector
> Professor of Medical Informatics
> School of Computer Science
> University of Manchester
> Manchester M13 9PL, UK
> TEL +44 (0) 161 275 6149/6188
> FAX +44 (0) 161 275 6204
> www.cs.man.ac.uk/~rector
> www.co-ode.org
> http://clahrc-gm.nihr.ac.uk/
>
>
>
>
>
>
>
Received on Thursday, 29 April 2010 22:00:37 GMT

This archive was generated by hypermail 2.3.1 : Wednesday, 27 March 2013 09:32:58 GMT