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

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

From: Henry S. Thompson <ht@inf.ed.ac.uk>
Date: Mon, 11 Oct 2004 23:35:18 +0100
To: Burak Emir <Burak.Emir@epfl.ch>
Cc: xmlschema-dev@w3.org, xml-dev@lists.xml.org
Message-ID: <f5bfz4khoih.fsf@erasmus.inf.ed.ac.uk>

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.

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.

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.


 Henry S. Thompson, HCRC Language Technology Group, University of Edinburgh
                     Half-time member of W3C Team
    2 Buccleuch Place, Edinburgh EH8 9LW, SCOTLAND -- (44) 131 650-4440
            Fax: (44) 131 650-4587, e-mail: ht@inf.ed.ac.uk
                   URL: http://www.ltg.ed.ac.uk/~ht/
[mail really from me _always_ has this .sig -- mail without it is forged spam]
Received on Monday, 11 October 2004 22:35:25 UTC

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