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  
loopholes.

>> 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  
acceptable.

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

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