I am trying to understand the example given here of an EXP-SPACE time decision problem.

They write :

An example of an EXPSPACE-complete problem is the problem of recognizing whether two regular expressions represent different languages, where the expressions are limited to four operators: union, concatenation, the Kleene star (zero or more copies of an expression), and squaring (two copies of an expression)

Here is what I understand. Supposing I have some alphabet $\Sigma = \{a,b,c...,z\}$, then a regular expression is a pattern in order to specify the set of strings that belong to some language.

So for instance if I have two regular expressions, say

$aa+a^{*}+bb^2$ then any string that satisfies this expression is in $L_1$ (language 1),

$abc$ then any string that satisfies this expression is in $L_2$

Why does determining if these languages are the same in the worst case take exponential space. Further what is the size of the input ? I imagine it could be the sum of lengths of the two reg-expressions, but I am not sure.

Edit: If the Kleene star criterion is dropped, then I could see that we could simply create a set with all possible strings (the power set), and then compare the two sets, not sure about the input size however.

  • $\begingroup$ Why is this problem EXPSPACE-hard? This requires a proof. Perhaps Wikipedia has a link to one. $\endgroup$ – Yuval Filmus Jan 31 at 4:18
  • $\begingroup$ @YuvalFilmus right, and here it is: people.csail.mit.edu/meyer/rsq.pdf, I will read this and try and give a sketch in the next few days or so. $\endgroup$ – IntegrateThis Jan 31 at 5:23

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.