Re: Complexity of :matches ?

Philip Guenther <guenther+mtafilters@sendmail.com> Tue, 12 July 2005 11:36 UTC

DomainKey-Signature: a=rsa-sha1; s=tls; d=sendmail.com; c=nofws; q=dns; b=raMoG4lUW+fS0LbUCSTPWEeRUVeIL3bSXiN0V9Mp6E0xjhCfTRVsUIhaijJ7UqlKr B1UNa4ZvHwW807+zRS816sWYHM1BYlBBW6WuJr/4rU2o943q3n8rGKwOw1GKYOgdfnS +PeV2pQyEXFf6Hr8kAJnpeFj2Leuf/XyozVQBHQ=
Message-Id: <200507121136.j6CBapWi042099@lab.smi.sendmail.com>
From: Philip Guenther <guenther+mtafilters@sendmail.com>
To: ietf-mta-filters@imc.org
Subject: Re: Complexity of :matches ?
In-reply-to: <200507121052.j6CAq1rH038682@lab.smi.sendmail.com>
References: <E1DsGVb-0003gO-Fg@nostromo.freenet-ag.de> <200507121052.j6CAq1rH038682@lab.smi.sendmail.com>
Date: Tue, 12 Jul 2005 04:36:51 -0700
Sender: owner-ietf-mta-filters@mail.imc.org
Precedence: bulk

I, Philip Guenther <guenther+mtafilters@sendmail.com> wrote:
...
>For an NFA, the setup is O(N) in time and space and matching is O(N*M).
>
>For a non-lazy DFA, the matching is O(M), but the worst-case setup is
>O(2^N).
...

I should note that the dragon book's statements, as I tried to
summarize above, are only true of the original, truly regular
"regular expressions" and not the extended or 'irregular' regular
expressions seen in most tools.

In particular, counted repetitions ({n,m}) have to be expanded when
figuring the 'N' of the size of the regexp, while back-references
(\digit) are, IIRC, worst-case exponential to match.  If you're
capturing matches then the POSIX matching rules apparently are
worst-case exponential on the number of characters in the regexp,
or something like that.

Philip Guenther

Re: Complexity of :matches ? Philip Guenther
Re: Complexity of :matches ? Michael Haardt
Re: Complexity of :matches ? Philip Guenther
Re: Complexity of :matches ? Michael Haardt
Complexity of :matches ? Michael Haardt
Re: Complexity of :matches ? Ned Freed
Re: Complexity of :matches ? Tim Showalter
Re: Complexity of :matches ? Michael Haardt
Re: Complexity of :matches ? Michael Haardt