W3C home > Mailing lists > Public > w3c-rdfcore-wg@w3.org > February 2003

Re: Comments on (informal) meaning of lists

From: pat hayes <phayes@ai.uwf.edu>
Date: Tue, 4 Feb 2003 14:29:43 -0600
Message-Id: <p05111b3aba65d1ec6b61@[]>
To: Graham Klyne <GK@NineByNine.org>
Cc: w3c-rdfcore-wg@w3.org

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


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

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 14:54:04 UTC