There are references on the exponential worst-case of the intersection operator for regular expressions (see [1]). However, I was wondering if there are similar results for the construction process itself?

Concretely, given two regular expressions $E_1$ and $E_2$ whose intersection can be represented by a regular expression of polynomial size, is the construction process itself bounded by exponential time or memory in the worst-case?

[1] Succinctness of the Complement and Intersection of Regular Expressions

  • 1
    $\begingroup$ Are you aware of the problem of minimizing a regex? $\endgroup$
    – plshelp
    Commented Aug 28, 2020 at 11:40
  • $\begingroup$ Or regex equality? $\endgroup$
    – plshelp
    Commented Aug 28, 2020 at 11:51
  • $\begingroup$ @plshelp thanks for the links! Could you elaborate a bit more on how do they imply an answer to my question? I don't quite see the reduction. $\endgroup$
    – user59861
    Commented Aug 31, 2020 at 8:44


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.