10
$\begingroup$

Let a number $n$ be given. Consider the following language $L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \}$.

In words, $L_n$ is the set of copy strings of length $2n$.

Consider the following state complexity function $s$ such that $s(n)$ is the number of states in the smallest Pushdown Automata that recognizes $L_n$.

Question: Can you formally prove any meaningful lower bound for $s(n)$?

My Conjecture: $s(n) = 2^{\Theta(n)}$.

Known Upperbound: $s(n) \leq \mathrm{poly}(n) \cdot 2^{\frac{n}{2}}$.

Rules:

(1) The stack alphabet must be binary.

(2) The input tape is one-way and can't stop on any input character.

$\endgroup$
  • $\begingroup$ I currently don't have any meaningful lower bound. It seems to me you might be able to prove a lower bound for the number of variables you need for a CFG that recognize the language. Although, I'm not even totally sure of this. $\endgroup$ – Michael Wehar Jul 23 '15 at 4:36
  • 1
    $\begingroup$ My intuition is that as you push characters from the input tape to the stack, you run into a problem. If you ever want to retrieve these bits later on, you have to throw away all the bits that you pushed above it. In other words, it appears that the stack doesn't help you because the more you push to it, the more you're forced to forget later on. $\endgroup$ – Michael Wehar Jul 23 '15 at 4:39
  • 1
    $\begingroup$ Remark: For DFA's (automata without a stack), you can prove an exponential state complexity lower bound. $\endgroup$ – Michael Wehar Jul 23 '15 at 4:45
  • 1
    $\begingroup$ Can you show a reasonable lower bound for the simpler problem of $\{0^k1^l0^k1^l\}$? $\endgroup$ – András Salamon Jul 23 '15 at 7:53
  • 1
    $\begingroup$ A more precise upper bound seems to be $(n+3)2^{n/2}$ states. $\endgroup$ – András Salamon Jul 25 '15 at 12:29
10
$\begingroup$

The technique described by Yuval:

Do there exists polynomial size CFG that describe this finite language?

( you may also read: Lower bounds on the size of CFGs for specific finite languages )

allows to show very easily an exponential lower bound for CFGs. Let $G$ a grammar in Chomsky Normal Form for $L_n$. For every word $w\in \{0,1\}^n$ there exists at least one non-terminal $A(w)$ accepting a subword $s(w)$ of $ww$ having length between $n/2$ and $n$. Let $p(w)$ be a position in $ww$ where this subword occurs. There are at least $n/2$ bits common to all words $w,w'$ such that $A(w)=A(w')$ and $p(w)=p(w')$. Consequently, there can be at most $2^{n/2}$ words that have the same $A(w)$ and $p(w)$. Hence there are at least $2^{\Theta(n)}$ non-terminals.

Furthermore, the PDA can be converted into a CFG in CNF, of polynomial size so this also gives the $2^{\Theta(n)}$ bound on the state complexity of $L_n$.

$\endgroup$
  • $\begingroup$ Awesome, thanks again! I see now and will think about it to confirm. :) $\endgroup$ – Michael Wehar Jul 24 '15 at 15:38
  • 2
    $\begingroup$ Right again: changing length from $[n,2n]$ to $[n/2,n]$ introduced another issue. I had to refine the argument in a way similar to Yuval's (counting overlaps). Now I believe it is correct, at last. I edited the answer and deleted my comments $\endgroup$ – Joseph Stack Jul 28 '15 at 8:46
  • 1
    $\begingroup$ In case it helps anyone else: note that once $(A(w),p(w))$ has been chosen, $A(w)$ can only ever yield the single subword of $ww$ that begins at position $p(w)$. So this actually shows that any correct CNF-CFG for this language must have many nonterminals that each generate a single long subword. $\endgroup$ – András Salamon Aug 4 '15 at 10:07
  • 2
    $\begingroup$ See also Theorem 7 in my paper: cs.toronto.edu/~yuvalf/CFG-LB.pdf. $\endgroup$ – Yuval Filmus Nov 15 '15 at 23:21
  • 1
    $\begingroup$ @YuvalFilmus It's worth also noting that Andras spent a bit of time trying to get the upper and lower bounds to match. My friend Pepe and I defined a general class of finite languages and applied the technique to them. We never wrote anything up though. If you ever have any related problems, we would be more than willing to collaborate. Thanks again. $\endgroup$ – Michael Wehar Nov 16 '15 at 3:13

Your Answer

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

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