Re: detecting a pattern for any?

On Sun, 4 Jan 2004 20:26:04 +0400 (AMT)
David Tolpin <[email protected]> wrote:

> 
> but got stuck trying to write the correct algorithm. What is the right way to do it?

It is not difficult to examine if a given regular tree grammar allows any tree.  
I am aware of two efficient algorithms.

	Haruo Hosoya. Regular Expression Types for XML. PhD thesis, The University of Tokyo, December 2000.
	http://www.kurims.kyoto-u.ac.jp/~hahosoya/papers/phdth.ps

	Akihiko Tozawa, Masami Hagiya: XML Schema Containment Checking Based on Semi-implicit 
	Techniques. CIAA 2003: 213-225

However, it is not easy to examine if a given RELAX NG grammar allows
any element.  There are three problems: attribute-element constraints,
interleave, and datatypes.   The next paper addresses the first, but does
not address the second and third.

	Haruo Hosoya and Makoto Murata. Validation and boolean operations for 
	attribute-element constraints. 
	In Programming Languages Technologies for XML (PLAN-X), pages 1-10, 2002.
	http://www.kurims.kyoto-u.ac.jp/~hahosoya/papers/attelm.ps

I am aware of some works in interleave, but nothing has been published yet.

Datatypes are just difficult.  However, practically, we can assume that xsd:string 
without facets allow any strings and the other datatypes disallows some strings.

Cheers,

-- 
MURATA Makoto <[email protected]>