Re: Complexity of :matches ?

[Michael Haardt <[e-mail]>]

> 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.

That's because back-references leave the class of regular languages,
but I am surprised right now that the manual does not say so.

This egrep expression shows that is an entertaining way:

^(aa+)\1+$

It does not match if the length of the string of a characters is prime,
because the group is a prime factor.  A DFA can not do that, because it
contains only a finite number of states, thus being unable to compute
with natural numbers.  I guess I should think less about regular
expressions. :)

Michael