Re: Safe user-facing pattern matching.

[Martin <eden_martin_fuhrspam@...>]

On 04/24/2017 12:12 PM, Gé Weijers wrote:
> Here's another problem:
>
>   "^a*(%bab)(%bbc)c*$"
>
> This won't match if the number of b's is larger than the sum of the
> numbers of a's and c's. And "%bab" matches "a-+abb", for instance,
> whereas "a*" won't match any letters except 'a'.

I didn't catch problem, could you provide sample strings that matched
and not matched by pattern?

> So of course there's an ad-hoc linear time algorithm to match this, but
> the point is: can we come up with a matching algorithm that writes that
> ad-hoc algorithm automatically, i.e. can we solve the general case?

I think the more common questions besides this are

  * does current regexps language is powerful enough to match all
    possible strings that can be matched in linear time?
    (probably not)
  * does such language exists?
  * could this language be constructed?

This recalls me Goedel's statement that on any complex enough
axioms basis may be assertions whose trueness or falseness
cannot be proved anyhow.

-- Martin