Re: Preliminary version of new regex matcher for gawk now available

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:

Well, I skimmed through the txt file on Mike's git page to learn
about the algorithm; especially the algorithm and its complexity
is of interest to me. The document was not quite clear about that
(or at least made me doubt) beyond the general and typical O(N*M)
characteristics. One thing I was astonished about was why there's
a non-deterministic automaton model used (NFSM can be transformed
into Deterministic FSM); isn't the non-deterministic tree-search
(where every branch is traversed breadth-first) sub-optimal?

The non-deterministic to deterministic transformation yields (at worst)
an exponential number of states.  Keeping track of a set of states is
usually the preferred method.

--
Ben.