title: Algorithm to find out whether the matches for two Glob patterns (or Regular Expressions) intersect
body: <p>I'm looking at matching glob-style patterns similar the what the <a href="http://redis.io/commands/keys" rel="nofollow noreferrer">Redis KEYS command accepts</a>. Quoting:</p>
  
  <blockquote>
    <ul>
    <li>h?llo matches hello, hallo and hxllo</li>
    <li>h*llo matches hllo and heeeello</li>
    <li>h[ae]llo matches hello and hallo, but not hillo</li>
    </ul>
  </blockquote>
  
  <p>But I am not matching against a text string, but matching the pattern against another pattern with all operators being meaningful on both ends.</p>
  
  <p>For example these patterns should match against each other in the same row:</p>
  
  <pre><code>prefix*       prefix:extended*
  *suffix       *:extended:suffix
  left*right    left*middle*right
  a*b*c         a*b*d*b*c
  hello*        *ok
  pre[ab]fix*   pre[bc]fix*
  </code></pre>
  
  <p>And these should not match:</p>
  
  <pre><code>prefix*       wrong:prefix:*
  *suffix       *suffix:wrong
  left*right    right*middle*left
  pre[ab]fix*   pre[xy]fix*
  ?*b*?         bcb
  </code></pre>
  
  <p>So I'm wondering ...</p>
  
  <ul>
  <li>if this is possible to do (implement a verification algorithm), if at all?</li>
  <li>if not possible, what subset of regex would be possible? (i.e. disallow * wildcard?)</li>
  <li>if it is indeed possible, what is an efficient algorithm?</li>
  <li>what are the time complexity required?</li>
  </ul>
  
  <hr>
  
  <p><strong>EDIT:</strong> Found <a href="https://stackoverflow.com/questions/6363397/how-to-tell-if-one-regular-expression-matches-a-subset-of-another-regular-expres/6364335#6364335">this other question on RegEx subset</a> but this is not exactly the same as the words that <code>hello*</code> and <code>*ok</code> matches is not a subset/superset of each other but they do intersect.</p>
  
  <p>So I guess mathematically, this might be phrased as; is it possible to deterministically check that a set of words that one pattern match, intersecting with a set of words that another pattern matches, result in a non-empty set?</p>
  
  <hr>
  
  <p><strong>EDIT:</strong> A friend <a href="https://stackoverflow.com/users/889578/neizod">@neizod</a> drew up this elimination table which neatly visualize what might be a potential/partial solution: <a href="http://pastebin.com/aBsGs5qd" rel="nofollow noreferrer">Elimination rule</a></p>
  
  <hr>
  
  <p><strong>EDIT:</strong> Will adds extra bounty for those who can also provide working code (in any language) and test cases that proves it.</p>
  
  <hr>
  
  <p><strong>EDIT:</strong> Added the ?*b*? test case discovered by @DanielGimenez in the comments.</p>