I don't think you need to even go as far as adding a modifier. A smart enough regex engine would know when it could use the linear runtime algorithm, and when it needs to fall back.
Hence my last example without the modifier & the comment saying it should work.
My claim was that there should be a modifier to demand a particular performance characteristic. i.e. "I want an error if I do something stupid"
Assuming that means that a library function exists to verify that no linearity-breaking features are used, you could also use that to validate user input, which may be good enough.
