My question concern's a statement from the classic paper The equivalence problem for regular expressions with squaring requires exponential space.

Regular expressions with squaring are like ordinary regular expression but with a squaring operation. Let $RSQ(\Sigma) = \{ E \mbox{ is a regex with squaring} : L(E) \ne \Sigma^{\ast} \}$ be the test if some RegEx with squaring describes every word. In the paper the following is shown:

Theorem 2.1: There is a finite set $\Sigma$ such that if $M$ is any machine which recognizes $RSQ(\Sigma)$, then there is a constant $c > 1$ such that $M$ requires space (and hence time) $c^n$ on some input of length $n$ for infinitely many $n$.

By coding accepting computations by such regular expressions they continue to show that if $L \subseteq \{0,1\}^*$ is any language with a space bound of $2^n$, then we can reduce the membership problem of $L$ to $RSQ(\Sigma)$ for some $\Sigma$ (the alphabet needs to be enlarged to account for describing sequences of instantaneous descriptions of Turing machines).

Then the argument for the above Theorem relies on the following fact (Fact 2 in the paper) taken from another paper:

Let $S_1(n)$, $S_2(n)$ be tape constructable functions such that $$ \inf_{n\to \infty} \frac{S_1(n)}{S_2(n)} = 0 \qquad \mbox{ and } S_2(n) \ge \log(n). $$ Then there is a language $L \subseteq \{0,1\}^*$ accepted by some space $S_2(n)$ machine but by no space $S_1(n)$ machine.

It is used in the following manner:

Proof of Theorem 2.1: let $L$ be as in Fact 2 [the statement above] with $S_2(n) = 2^n$. Let $\Sigma$ be such that $L$ reduces to $RSQ(\Sigma)$.

If $RSQ(\Sigma)$ is accepted by some space $S(n)$ machine, then $L$ is accepted by some space $S(cn) + cn$ machine for some constant $c$ [this is a general property of reductions as stated earlier]. $$ \inf_{n\to \infty} \frac{S(cn) + cn}{2^n} > 0 $$ implies that $S(n) \ge d^n$ for some constant $d > 1$ and all $n$ which are multiples of $c$.

How do they know that $\inf_{n\to \infty} \frac{S(cn) + cn}{2^n} > 0$? Somehow the order of quantifiers in the statement of the fact seem not to match that kind of deduction. It does not say that if we have any machine with $S'(n)$ which also accepts $L$ then we must have $$ \inf_{n\to \infty} \frac{S'(n)}{S(n)} > 0. $$ It just says that if this equals zero, then we can choose some language accepted in space bound $S(n)$ but not in space bound $S'(n)$, so it depends on the firstly choosen $S'(n)$. But the argument of the proof does not seem to use it that way. Also the introduction "Let $L$ be as in Fact 2 [...]" seems problematic, for what space bound function $S'(n)$ in the numerator is $L$ choosen?

So how do this argument works? What am I missing here? Can someone please explain?

EDIT: Just let me add that if I accept $\inf_{n\to \infty} \frac{S(cn) + cn}{2^n} > 0$ then $S(n) \ge d^n$ for some $d > 1$ and all multiplies of $c$ is clear to me. For then we know for some $\varepsilon > 0$ we have $$ S(cn) > 2^n\varepsilon - cn $$ for all $n > N$ for some $N$. Write with $d > 1$ then $2^n = (d + \delta)^n \ge d^n + n d^{n-1}\delta \ge d^n + d^{n-1}\delta$ and as $\lim_{n\to \infty} \frac{c\varepsilon^{-1}n}{d^{n-1}} = 0$ we have $c\varepsilon^{-1}n \le d^{n-1}\delta$ for all $n$ sufficiently large, which gives $S(cn) \ge \varepsilon d^n$. Now choose $1 < \hat d < d$ and we find $\lim_{n\to \infty} \frac{\hat d^n}{\varepsilon d^n} = 0$, hence $\varepsilon d^n \ge \hat d^n$ for sufficiently large $n$. So understanding the following conclusions is not the problem.


1 Answer 1


Here's one simple resolution. The statement referred to as "Fact 2" is a slightly weaker form of the standard Space Hierarchy Theorem. The standard version of the Space Hierarchy Theorem has the quantifiers rearranged:

For every space-constructible $S_2(n)$, there exists $L \in \mathbf{DSPACE}(S_2(n))$ such that for every space constructible $S_1(n) \leq o(S_2(n))$, $L \not \in \mathbf{DSPACE}(S_1(n))$.

  • $\begingroup$ You mean they are actually using this theorem, hence this seems to be a typo in the paper? $\endgroup$
    – StefanH
    Commented Mar 1, 2019 at 11:03
  • $\begingroup$ Yes, I think that's a reasonable interpretation. $\endgroup$ Commented Mar 2, 2019 at 22:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.