recursive shapes in shape expressions

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Shape Expressions includes recursive shapes, such as
  <IssueShape> {
    :status (:Assigned :Unassigned),
    ... ,
    :related @<IssueShape>*
  }
Recursive shapes are a prominent feature of Shape Expressions, showing up in
the introductory material and talks about Shape Expressions.  However, there
appears to be problems in the semantics of recursive shapes in Shape
Expressions.  If these problems cannot be fixed, then recursive shapes may
have to be removed from Shape Expressions.

Sometimes it is relatively obvious what nodes are have such recursive
shapes.  For example, in
  ex:i1 :related ex:i2 .
  ex:i1 :related ex:i3 .
  ex:i1 :status :Assigned .
  ex:i2 :status :Unassigned .
  ex:i3 :status :Unassigned .
all of ex:i1, ex:i2, and ex:i3 should have shape <IssueShape>.

Do ex:j1, ex:i2, and ex:i3 have shape <IssueShape> here in Shape
Expressions?  Show how this can be determined in each of the semantics for
Shape Expressions.

However, sometimes it is not obvious what nodes have a particular
recursive shape.  For example, in
  ex:j1 :related ex:j1 .
  ex:j1 :status :Assigned .
it is reasonable to consider ex:j1 as having shape <IssueShape> but it is
also reasonable to consider ex:j1 as not having shape <IssueShape>.

Does ex:j1 have shape <IssueShape> here in Shape Expressions?   Show how this
can be determined in each of the semantics for Shape Expressions.

There are ever trickier situations involving recursive shapes.  For example,
consider the two mutually recursive shapes
  <S> { ( ex:p @<S> | ex:p @<T> ) }
  <T> { ( ex:p @<T> | ex:p @<S> ) }
(something is in <S> if it has an ex:p fillers and either all its ex:p
fillers are in <S> or its ex:p fillers are in <T> but not both, and
similarly for <T>).  It is unclear as to which nodes should have shape <S>
or <T> in the graph
  ex:a ex:p ex:b .
  ex:b ex:p ex:a .

Which nodes have which shapes here?  Show how this can be determined in each
of the semantics for Shape Expressions.  Are the answers independent of
changes in the ordering of the disjuncts?  Do the answers depend on any
ordering of the sets involved?  Does this match any intuitive notion of
recursive shapes?


Here are another couple of situations that should be considered as well.

  <A> { ( ex:p1 <B> | ex:p2 <B> ) }
  <B> { ex:q <B> }
  ex:a ex:p1 ex:b1 .
  ex:a ex:p2 ex:b2 .
  ex:b1 ex:q ex:b2 .
  ex:b2 ex:q ex:b1 .

  <A> { ( ex:p1 <B> | ex:p2 <B> ) }
  <B> { ( ex:q <B> | ex:r { ex:c } ) }
  ex:a ex:p1 ex:b1 .
  ex:a ex:p2 ex:b2 .
  ex:b1 ex:q ex:b2 .
  ex:b1 ex:r ex:c .
  ex:b2 ex:q ex:b1 .
  ex:b2 ex:r ex:c .



peter
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQEcBAEBAgAGBQJU6QZoAAoJECjN6+QThfjziwEIALlbN9lAZwJz57AncuUA2HdF
QYceD3oL0N2Ul7rJAgf//xdApw2bYqnwG+YFAIokEZRj6jLNjmxcqojxnpoNKGrS
g4iVvCDrzOShr2NyapX/Pv1PxUbC6Jn2jIjZiT0OLDfkxXqc3QwkoDd7u4zLffML
DXHUl1D1OhbDlQGz6NjRwPV41w/1PjsJUaFhwLE5aRO6Y13S1aC+EjhpuPQIV+Tw
Coc9c3NhdVZNwEzGXzveO+QKwjqkJmE/C+rFoT1B29D1eBeAsJ42u+iYl2Q1/d04
O+7y/Nn1ky7QU3uMYYbVCx3U9CToLwnXsQbLy2tFZUw73tjfVg5h8ebQDJwTDGc=
=HUtg
-----END PGP SIGNATURE-----

Received on Saturday, 21 February 2015 22:28:24 UTC