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 Aug 28 '20 at 11:40
  • $\begingroup$ Or regex equality? $\endgroup$ – plshelp Aug 28 '20 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 Aug 31 '20 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy