xsl-list
[Top] [All Lists]

Re: [xsl] Kleene Operators

2010-03-01 11:14:11
Thank you for responding. Remarks below.



----- Original Message ----
From: Michael Kay <mike(_at_)saxonica(_dot_)com>
To: xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com
Sent: Mon, March 1, 2010 4:00:57 AM
Subject: RE: [xsl] Kleene Operators

I am lucky to have an adjunct teaching job at RIT teaching 
xml and xsl and started to think about the questions they 
might ask me about why do we use *,+,?  and wondered if there 
was some really good answer rather than the operators result 
in a closed set. I like the construct and would not imagine I 
would have something better or different to offer.

Firstly, I'm surprised that you desribe these operators as coming out of set
theory. I thought they were all to do with the structure of sequences. But
I'm not really sure what the boundaries of "set theory" are supposed to
be...

What little I understood I got from here:
http://en.wikipedia.org/wiki/Kleene_star and http://en.wikipedia.org/wiki/Monoid
and from the second one I saw ...superscript * is the Kleene star: the set is 
closed under composition or concatenation of its elements... and made a jump to 
sets. 

Fundamentally, if you take the view that the only interesting numbers are
zero, one, and infinity, then the interesting cardinality bounds on finite
sequences are

  (0, 0)
(0, 1)
  (0, infinity)
  (1, 1)
  (1, infinity)

giving five ranges which one might denote as Xº, X?, X*, X¹, X+. In the
Kleene system, the (0, 0) case is not provided for presumably because it is
only of theoretical interest, and the (1, 1) case doesn't get a symbol
because it's the default. But I've been using Xº and X¹ internally.

When you say "the operators result in a closed set", I'm wondering exactly
what you you have in mind?

I think the second reference sent me off in that direction; the strings being 
operated on that are in the set. 

I guess there's an intersection operator whereby
X¹.X? = X¹, X?.X? = X?, X?.X* = X?, X?.X+ = X¹; and a union operator whereby
X?|X+ = X*, etc. But if you include Xº, then Xº.X+ doesn't have an
intersection within the group: Xº represents the set of empty sequences, X+
the set of non-empty sequences, and their intersection is the empty set,
which isn't part of the group.

I guess on our xml world a null set just vanishes. 
Used in a DTD the *,+,? are just a great way to formalize what people will be 
allowed to do when they create content and leave it at that. 

Regards,

Michael Kay
http://www.saxonica.com/
http://twitter.com/michaelhkay 


--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--


      

--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--

<Prev in Thread] Current Thread [Next in Thread>