W3C home > Mailing lists > Public > xmlschema-dev@w3.org > October 2004

Re: [xml-dev] New release (2.8) of XSV

From: Burak Emir <Burak.Emir@epfl.ch>
Date: Wed, 13 Oct 2004 10:54:21 +0200
Message-ID: <416CED3D.2090201@epfl.ch>
To: "Henry S. Thompson" <ht@inf.ed.ac.uk>
CC: xmlschema-dev@w3.org, xml-dev@epfl.ch

Henry S. Thompson wrote:

>Thanks very much!  We did indeed start from the Aho&Ullman ~ Thompson
>(not me, the other one) Regexp->NDFA algorithm, which uses epsilons
>freely, and then determinised the result.
As Michael Kay said, it's good to see some applied theory. Without that 
work, how could there be discussion and improvement.

Are these automata with counters also used for checking language 
inclusion and left-factor-ness (erm, restriction and extension)?

>I do think the unfolding construction is (space) exponential in the
>depth of embedding, but I may be mis-remembering -- it's certainly
>_not_ linear in the number of particles.
Well, thinking again, I see what you mean, it is exponential in the 
depth of nesting (if every nesting introduces some exponent!).

I was considering that nesting indicates the presence of more particles 
anyway (to satisfy 1-unambiguousness), so there are already more 
particles. But then nesting introduces a constant number of particles, 
and the {m,n} exponent multiplies this constant in each nesting.

Before getting entangled in this, it is probably better writing it up, 
so one can be precise. Without any doubt, adding counters brings a lot :-)

>I didn't know about Sethi&Berry, will follow up the reference.
>I did look pretty hard for prior work on (Regexp+numeric
>exponents)->FSA+counters, but couldn't find any -- if you know of any
>I'd very much welcome a pointer.
Unfortunately, I don't know literature on things like a{n,m} either.

Most researchers interested in finite automata and counting jump to 
logics with Presburger's constraints.
However, this goes well beyond regular expressions, and thus is not a 
big help.

An adaptation of Berry&Sethi with counting seems useful, and possible. 
We should follow up on this.


Received on Wednesday, 13 October 2004 08:54:25 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 14:56:06 UTC