Re: [xml-dev] interleave algorithm?

[Joe English <jenglish@flightlab.com>]

Gary Stephenson wrote:
>
> I am trying to implement Relax NG, but am having a hard time
> figuring out how to implement the "interleave" pattern.

The implementation depends on how you're implementing
the *rest* of Relax-NG.  'Interleave' is probably easiest
to implement if you're using an algebraic approach.
The reduction rule is:

    (e1 ^ e2) \ sym = ((e1 \ sym) ^ e2) | (e1 ^ (e2 \ sym))

(where '^' = interleave, | = union, and \ is the transition operator).

The following simplification rules also hold:

    (e ^ 0) = (0 ^ e) = 0
    (e ^ 1) = (1 ^ e) = e


You need to take some care if you're using a finite automaton
based algorithm, since expressions involving '^' can generate
extremely large numbers of states.  One approach is to represent
states in M(e1 ^ e2) as _pairs_ of states drawn from M(e1) x M(e2).

> Are there any published algorigthms or open-source implementations
> of a similar nature that I could access and study?  (for free!)

James Clark's TREX might be a good place to start.


--Joe English

  jenglish@flightlab.com