> You could have a situation where a query's termination depends on the optimisations used. IMHO, this is highly undesirable. Termination and exponential (or s

> You could have a situation where a query's termination depends on the optimisations used. IMHO, this is highly undesirable. Termination and exponential (or super-exponential) running times are about equally bad. Avoiding either is done on a case-by-case basis. Restricting the language can save you from one and not the other. > If we have a true regular language, we can optimise it via a DFA to have O(N) runtime. The weak computational model is enabling this optimisation. I'm not an expert on regex by any means, but I believe this optimization is exponential (a DFA can be exponential in the size of the regex), and so infeasible in practice. Regardless, as I said, regex is about as far down as we can take computation, and regexps make for a very poor generally useful computational construct.