User-Agent: Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.6; sv-SE; rv:1.9.2.28)
            Gecko/20120306 Thunderbird/3.1.20
MIME-Version: 1.0
References: <CACKZBPX-udskZ1JNVDwBzgFOfS8wMr3cBw9JwMbZwuLodfS5=A@mail.gmail.com>           
            <5268D3D0.1050209@residenset.net>
            <CACKZBPX-UXh+s5nXbTuXPDi4rCMFbs_ebjjDPufu5RSJ+xD2FA@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Message-ID:  <52693F2A.80902@residenset.net>
Date:         Thu, 24 Oct 2013 17:39:22 +0200
Reply-To: Mailing list for the LaTeX3 project
              <LATEX-L@LISTSERV.UNI-HEIDELBERG.DE>
Sender: Mailing list for the LaTeX3 project <LATEX-L@LISTSERV.UNI-HEIDELBERG.DE>
From: =?ISO-8859-1?Q?Lars_Hellstr=F6m?= <Lars.Hellstrom@RESIDENSET.NET>
Subject: Re: l3regex feature request + a question about the implementation
To: LATEX-L@LISTSERV.UNI-HEIDELBERG.DE
In-Reply-To:  <CACKZBPX-UXh+s5nXbTuXPDi4rCMFbs_ebjjDPufu5RSJ+xD2FA@mail.gmail.com>
Precedence: list
Content-Transfer-Encoding: quoted-printable
Envelope-To: <rainer.schoepf@GMX.NET>
Status: R

Michiel Helvensteijn skrev 2013-10-24 13.43:
> On Thu, Oct 24, 2013 at 10:01 AM, Lars Hellstr=F6m
> <Lars.Hellstrom@residenset.net>  wrote:
>> An optimal approach for your setting would perhaps be a lazy powerset
>> construction: don't carry it out for a particular state in the DFA unt=
il you
>> actually reach that state
during matching (should I perhaps have added for clarity)
>> , but then record the result; matching typically
>> doesn't reach all the states of the DFA, since you don't match against
>> arbitrary data. This, however, assumes that you have some efficient me=
thod
>> of memoising the results from lazy computations. (I suppose a family o=
f
>> control sequence names could do the trick.)
>
> Interesting, I haven't come across the idea of a lazy powerset
> construction before. But I don't think I fully understand what you are
> proposing. Using "a family of csnames" suggests to me the general
> technique of maintaining an input-output table for a pure function.

I was thinking one csname per state of the DFA (subset of states of the=20
NFA), that in turn acted as a function from input character to new state =
of=20
DFA. This should work perfectly well in your one-token-at-a-time setting.

> But that would only memoize exact inputs; variations on the same
> pattern wouldn't get any benefit, and it wouldn't work in my setting
> anyway, where I get one token at a time. My current implementation
> uses a "trie" datastructure, which might be one step better than a
> simple table. But still not good enough by far, I think.
>
> When I first read the term "lazy powerset construction" in your post,
> I imagined restructuring the automaton on-the-fly somehow, which
> sounded pretty cool.

In my experience, most operations on automata tend to produce automata wi=
th=20
epsilon-transitions, which one then at some cost (not cool) has to get ri=
d=20
of before executing them. Unless the operation does something even worse =
to=20
the state set... :-(

> (2) I would also need the ability to merge new (N|D)FA's into an
> existing one and mark the corresponding accepting states with an
> identifier. I could then query this identifier when a match was found,
> so I could know which original pattern(s) matched.

Doable, but whichever way you do it, you effectively end up executing all=
=20
the component automata in parallel. With DFAs, the new state space is the=
=20
cartesian product of the component state spaces. With NFAs, you have a se=
t=20
of active branches for each component automaton. So if you're anyway feed=
ing=20
data to your automaton one token at a time, then you might as well feed e=
ach=20
token to a sequence of automata instead.

Lars Hellstr=F6m