Re: preliminary analysis of shape expressions proposal

Hash: SHA256

On 05/05/2015 03:45 PM, Iovka Boneva wrote:
> Dear Peter, all,

> The basic technical idea of the semantics is that nodes in a graph are 
> assigned zero or more shape labels and then the elements of these 
> assignments have to be backed up with local derivations that cover all
> the outgoing edges from a node and are consonant with the shape labels
> assigned to neighbouring nodes.  This gets around problems with
> ill-foundedness of recursive shapes.
>> There is no problem with recursion. Peter, as you already realized
>> earlier, there was a problem with recursion in the initial Eric's shape
>> expressions, because of the 'exclusive or' (so hidden negation)
>> combined with recursion. On the other hand, I think I convinced you
>> earlier that there is no problem with recursion and the 'normal'
>> disjunction that we currently have in the language. Because a choice of
>> only one among several (kind of 'exclusive or') is useful in the use
>> cases, we added the 'one-of' operator, for which we impose a syntactic
>> restriction that limits the use of recursion, while guaranteeing a 
>> sound semantics.

The Shape Expressions 1.0 Definition
is ill-founded even without negation or exclusive or.  Jose's
axiomatizations get around this problem but have their own problems with
recursive shapes and negation (including exclusive or).

I would thus say that there are indeed exhibited problems with recursion and
shape recognition.  These problems can be overcome in one way or another -
Description Logics, for example, used one way to get around the problems and
this solution is now so ingrained in the Description Logic community that
there is little evidence that there once was a big debate on how to solve
problems with recursive concepts in Description Logics.


Version: GnuPG v2


Received on Wednesday, 6 May 2015 04:20:33 UTC