Taxonomy of schema languages and validation algorithms

I hope that this paper (submitted to Extreme) helps to understand 
validation algorithms for schema languages such as RELAX and TREX.  
(You might have seen earlier versions of this paper, but this 
is away more readable.)

http://www.cs.ucla.edu/~mani/xml/mura0106.ps

In my understanding, Algorithm 4.1 shown in this paper is similar to 
the algorithms of PyTREX, VBRELAX, and XDuce.  The algorithm 
of RELAX Verifier for Java is based on Algorithm 5, but is more 
advanced.  The algorithm of JTREX is more advanced than Algorithm 
5 in that it constructs tree automata lazily.  In the final version, 
I will try to add more information about JTREX.

Cheers,

Makoto