4
$\begingroup$

I have read that minimizing regular expressions is, in general, PSPACE-complete. Is it known whether minimizing regular expressions without the Kleene closure (star, asterisk) is in P?

The language of any such regular expression would be guaranteed to be finite. I suppose an equivalent question is whether the problem of constructing a minimal regular expression from a known finite language is any easier than minimizing an arbitrary regular expression. It seems like this should be the case.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.