Lists Home |
Date Index |
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: email@example.com
[mail really from me _always_ has this .sig -- mail without it is forged spam]