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.

Improve this question
$\endgroup$
7
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 12:29

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Awesome, thanks again! I see now and will think about it to confirm. :) $\endgroup$
    – Michael Wehar
    Jul 24, 2015 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, 2015 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, 2015 at 10:07
  • 2
    $\begingroup$ See also Theorem 7 in my paper: cs.toronto.edu/~yuvalf/CFG-LB.pdf. $\endgroup$
    – Yuval Filmus
    Nov 15, 2015 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, 2015 at 3:13

Your Answer

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

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