title: Polynomial time algorithm for computing the size of the DFA describing the intersection of two regular expressions?
body: <p>The DFA describing the intersection of two regular expressions can be exponentially large compared to the DFAs of the regular expressions themselves.  (<a href="https://github.com/qntm/greenery" rel="nofollow noreferrer">Here's</a> a nice Python library for computing it.)  Is there a way to compute the size of the DFA for the intersection without needing exponential resources?</p>