Re: Comments on (informal) meaning of lists

>At 09:11 AM 2/3/03 -0800, pat hayes wrote:
>
>>Concerning the notion of 'well-formed' lists, there is a 
>>characterization of the RDF graphs which describe such lists in the 
>>relevant section of the semantics document.  Here is a more exact 
>>and careful statement of that characterization.
>>
>>Define a 'link' in a graph G to be a subgraph consisting of two 
>>triples of the form
>>
>>aaa rdf:first bbb .
>>aaa rdf:rest ccc .
>>
>>where ccc may be rdf:nil, but otherwise aaa and ccc are bnodes or 
>>urirefs which are not in the RDFS namespace. Call aaa the *addr* of 
>>the link, bbb the *head* of the link, and ccc the *tail* of the 
>>link. Define a 'line' in G to be a finite subgraph of G consisting 
>>of links and satisfying the following conditions: exactly one link 
>>in the line has rdf:nil as its tail; otherwise, every link's tail 
>>is the addr of exactly one other link in G; one link in the line 
>>has an addr which is not a tail of any other link - call this the 
>>*addr of the line* - and otherwise, the addr of every link in the 
>>line is the tail of exactly one other link in G; and no addr or 
>>tail (except rdf:nil) in the line occurs as the subject or object 
>>of rdf:first or rdf:rest elsewhere in G.
>
>Ummm...  I assume this is intended to describe a "well-formed list" 
>-- it's not obvious to me (other than by prior experience) what part 
>of this is a well formed list.
>
>I don't recognize anything here that prevents the following:
>
>   aaa rdf:first bbb .
>   aaa rdf:rest ccc .
>   aaa rdf:first ddd .
>
>being regarded as two distinct links:
>
>   aaa rdf:first bbb .
>   aaa rdf:rest ccc .
>
>   aaa rdf:first ddd .
>   aaa rdf:rest ccc .
>
>in that these are both subgraphs of the original.

True, I should have said that the links in any line are disjoint, ie 
define a line as a set of *disjoint* links.

>
>You talk of the *addr of the line* as being a link that is not the 
>tail of any other link.  Why this restriction?  Isn't every link the 
>head of some line?

Yes, but each line has a unique link containing its addr.

>
>...
>
>I'm not really comfortable with this description;  it seems easier 
>to me to adopt a recursive strategy:
>
>(a) a *link* in G is a subgraph of the form
>    aaa rdf:first bbb .
>    aaa rdf:rest ccc .
>where aaa denotes an object of type rdf:List, and
>there are no other statements in G of the form:
>    aaa rdf:first yyy .
>or
>    aaa rdf:rest zzz .
>Call aaa the *addr* of the link, bbb the *head* of the link, and ccc 
>the *tail* of the link.
>
>(b) a (well-formed) *line* is one of the following:
>
>    (i)  rdf:nil
>    (ii) a *link* whose head is any node, and whose *tail* is a 
>(well-formed) *line*.

Yes, that is rather neat. They are equivalent on finite graphs, but 
yours is more elegantly stated.

>
>>Given any line, the sequence of denotations of the heads of links 
>>obtained by starting with the addr of the line and following the 
>>tails in order, is the *list denoted by the line*.  Semantic 
>>extensions of RDF may well want to require that addrs of lines 
>>denote the list denoted by the line.
>
>(I considered offering a recursive definition for the list thus 
>denoted, but that seems unnecessary.)
>
>>This allows the heads of links to be the addrs of other lines, so 
>>it allows arbitrary S-expressions, in LISP parlance. To restrict 
>>oneself to 'linear' lists, add the condition that no head of any 
>>link in the line occur as the subject of any rdf collection 
>>property in G.
>
>I'm assuming we'll allow full s-expressions.  DO we need to say 
>anything explicitly about this -- I think it follows from the 
>(intended) definition.

Yes, but all the applications Ive seen (eg DAML, OWL) only need 
linear lists, so I suspect many folk will appreciate a concise way to 
state that restriction, is all.

Pat

-- 
---------------------------------------------------------------------
IHMC					(850)434 8903 or (650)494 3973   home
40 South Alcaniz St.			(850)202 4416   office
Pensacola              			(850)202 4440   fax
FL 32501           				(850)291 0667    cell
phayes@ai.uwf.edu	          http://www.coginst.uwf.edu/~phayes
s.pam@ai.uwf.edu   for spam

Received on Tuesday, 4 February 2003 15:28:02 UTC