Subject: A theory problem From: Kay Michael <Michael.Kay@xxxxxxx> Date: Thu, 28 Oct 1999 10:20:25 +0100 |
I sometimes get asked for suggestions for student projects, so if there are any budding theoreticians out there, or professors trying to teach theory, here's a little problem I want to know the answer to. It's prompted by the recent discovery of a bug in SAXON. The problem is as follows: A path expression returns a nodeset. There is a "natural order" to the result which is obtained by following the steps in a particular sequence. For some path expressions the natural order will always be the same as document order, for others it will not. Provide an algorithm that examines a path expression and determines whether it will always return nodes in document order. Here are some examples of path expressions that have this property: child::X parent::X following::X descendant::X following-sibling::X child::X/child::Y child::X/descendant::Y following-sibling::X/child::Y parent::X/descendant::Y child::X/child::Y/child::Z and here are some that don't: ancestor::X preceding::X descendant::X/child::Y child::X/following-sibling::Y descendant::X/parent::Y I can't see a pattern emerging, and where the path has more than two components I don't think I can rely on intuition any more, it needs some formal proof. (I do know that I haven't stated the problem fully, in that I haven't defined the "natural order" of a step such as descendants::X. A more formal statement of the problem must obviously form part of any proof). The motivation, of course, is that in SAXON I want to avoid doing a sort whenever possible. The prize for the winning entry is that the algorithm gets out into the wild! Mike Kay XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
XSL navigation in XML tree problem , Jean-Robert Wiame | Thread | Re: A theory problem, James Clark |
RE: Apply XSL on HTML/MathML ?, Bernhard Keil | Date | RE: Remove duplicates from a list, Kay Michael |
Month |