A theory problem

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