> Another practical usage I've heard: match "string" or 'string', but not "string'.<p>You don't need backreferences for that:<p><pre><code> '[^']*'|"[^"]*"</code></pre>
This reduction is really cool. I love reductions like this.<p>Is there a general consensus to use "regular expression" to refer to the actual regular ones and "regex" to refer to the non-regular variants?
One of the cool features of SAT problems is that they always terminate (if you're patient enough). Aren't regex, especially with backreferences, Turing-complete though? If so, they could be caught in an infinite loop, meaning they are more general than the SAT problem.
That "popcnt1" is also known as a 1-hot constraint.<p><a href="https://en.m.wikipedia.org/wiki/One-hot" rel="nofollow">https://en.m.wikipedia.org/wiki/One-hot</a>