[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: interleave algorithm?

• From: Joe English <jenglish@f...>
• To: xml-dev@l...
• Date: Tue, 16 Oct 2001 07:39:38 -0700

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

• Follow-Ups:
  • Re: interleave algorithm?
    • From: Gary Stephenson <garys@i...>

• References:
  • interleave algorithm?
    • From: Gary Stephenson <garys@i...>

• Prev by Date: Re: Cutting special deals for open source developers --noway!
• Next by Date: PSVI using existing infoset items
• Previous by thread: Re: interleave algorithm?
• Next by thread: Re: interleave algorithm?
• Index(es):
  • Date
  • Thread