[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Safe user-facing pattern matching.
- From: Martin <eden_martin_fuhrspam@...>
- Date: Fri, 28 Apr 2017 23:44:54 -0700
On 04/24/2017 12:12 PM, Gé Weijers wrote:
> Here's another problem:
> 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?
* 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.