Path: ...!3.eu.feeder.erje.net!feeder.erje.net!news.in-chemnitz.de!news.swapon.de!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben@bsb.me.uk>
Newsgroups: comp.lang.awk
Subject: Re: Preliminary version of new regex matcher for gawk now available
Date: Fri, 26 Jul 2024 10:57:43 +0100
Organization: A noiseless patient Spider
Lines: 17
Message-ID: <87h6cc5vc8.fsf@bsb.me.uk>
References: <66a21e7e$0$710$14726298@news.sunsite.dk>
	<v7tf29$2984r$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Fri, 26 Jul 2024 11:57:43 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="2f0e8b887f2208b0f5219b8ab3d9a2ba";
	logging-data="2931602"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+6KW05qHqhswk+CJPBfKqV/nCl7QytUAs="
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:5yuF6Scb1jOkqpAnLRy9QU2nhJM=
	sha1:lgIBAoCRFoEK9rp/cO386Vl+6AM=
X-BSB-Auth: 1.c4a4489c72c318f7f649.20240726105743BST.87h6cc5vc8.fsf@bsb.me.uk
Bytes: 1906

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.