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 14:51:43 -0700
Cc: Owl Dev <public-owl-dev@w3.org>, sonic@tcs.inf.tu-dresden.de
Message-Id: <776A0982-6781-4533-A8AE-86BC787D3816@berkeleybop.org>
To: Bijan Parsia <bparsia@cs.man.ac.uk>

On Apr 29, 2010, at 5:58 AM, Bijan Parsia wrote:

> It's been a while since I thought about LCS in expressive logics  
> (i.e., with disjunction...)
> 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.
> Well  you have to be a bit careful since just ruling out explicit  
> disjunctions is obviously not sufficient, e.g.,
> 	De Morgan's could bite you, "not C and not D"
> 	Axioms can bite you, i.e., you return C but C is defined to be D or  
> E.
> So you really have to be careful.

Good point. I'd be happy if the input ontology and the results used  
something like EL or some subset that prohibits these kinds of  

>> 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.
> It's typically both expensive to compute, is "Sensible" only for  
> very restricted logics, and maybe isn't as immediately useful as it  
> might seem.
> [snip]
>> 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.
> So my first question is about what you need it for and whether true  
> LCS is what you need.

The immediate application is semantic similarity (of which there are  
many many measures; the ones I am particularly interested in involve  
calculation of a LCS). An approximation of an LCS may be perfectly  

> Cheers,
> Bijan.
Received on Thursday, 29 April 2010 21:52:18 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 20:58:19 UTC