OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help



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

[ Lists Home | Date Index | Thread 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: 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]


News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 2001 XML.org. This site is hosted by OASIS