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

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.

Thanks

ht
-- 
 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