## Can a polynomial size CFG describe the finite language \{$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed\} over alphabet \{0,1\}?

Can a polynomial size Context free grammar describe the finite language {$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed} over alphabet of {0,1}?

One case this is possible is when $\pi(w)$ is the string reverse permutation (CFG is describing palindromes).

Are there other choices for $\pi(w)$ with polynomial size CFGs?

Explanation: $n$ and $\pi$ are fixed per language. $\pi$ depends on $n$ (the indices of the letters of $\pi(w)$ are a permutation of {1..n} corresponding to indices {1..n} in $w$). How is $\pi$ fixed - two sub-cases:

1. The answerer can choose $\pi$ (or a class of $\pi$s), having in mind the string reverse case is solved.
2. $\pi$ can vary over all permutations. Again, $\pi$ is fixed per language.

Any references to what languages can be described by polynomial size CFGs (I found only several papers by Asveld, P.R.J. dealing with permutations and circular shifts over large alphabets).

Polynomial size is defined as the size of the Chomsky Normal Form. I included CNF on purpose. In case several answers are given, the size of the CNF will show the smaller'' solution.

-
polynomial size in what? $n$? And is $n$ encoded in binary? It seems the CNF grammar is what you're seeking given the permutation $\pi$ and the length of the strings $n$. – Mitch Harris Jan 31 2011 at 16:22
cross-posted in math.stackexchange: math.stackexchange.com/questions/19691/… – Yuval Filmus Jan 31 2011 at 18:36
@Mitch: yes, polynomial in $n$ which is the length of $w$. You are even free to choose $\pi$ having in mind the string reverse case is solved. I don't thing the encoding of $n$ matters, the value matters. – jerr18 Feb 1 2011 at 6:49
not clear to me that this is doable when pi is identity. – Suresh Venkat Feb 6 2011 at 0:01

Quoting chandok's answer on MO in community wiki mode.

I think a more precise question would be :

Given a permutation $\pi$ of {1...n}, what is the size of a grammar describing $L_\pi = {w\pi (w), |w|=n}$.

In fact, there is not a lot of ways to build such a grammar : if you use a symbol that can develop into different words, i.e. that can put either a 0 or a 1 in a certain position of the final word, then that symbol has to take care simultaneously of the corresponding position in the other half of the word. This means that the only way to have a nontrivial rule is when the permutation $\pi$ has a property $$\pi({n-k+1...n}) = {1...k}$$ If this is the case we can split the permutation into two components $\sigma$ and $\tau$ such that : $$\forall i \in {1..k}, \pi(n-k+i) = \sigma(i) \quad \text{and} \quad \forall j \in {1...n-k}, \pi(j) = k+\tau(j)$$ Then, we can use the fact that $L_\pi = \bigcup_{|w|=n-k} w L_\sigma \tau(w)$

For example, with $rev_n$, the reverse permutation on {1...n}, we do have $rev_n({2...n}) = {1...n-1}$, thus we get the equality $L_{rev_n} = 0L_{rev_{n-1}}0 + 1L_{rev_{n-1}}1$, which translates into a linear sized grammar for $L_{rev_n}$.

In the general case, you get exponentially bigger grammar rules as you have to decide on a greater number of letters of $w$ at the same time. The worst case (which happens pretty often) is when you can't write any non-trivial rule, and then have to enumerate all the words of $L_\pi$, for example if $\pi = id_n$. The better cases are the permutation that are close to the reverse permutation for example if n is even and $\pi(i) = (n-i+1+(-1)^i))$

Edit : Let me give a more precise estimation of the size of such a grammar. Define S to be the subset of {0...n} consisting of those integers k such that $\pi({n-k+1...n}) = {1...k}$. S = {k1=0, k2, ..., kp = n} (0 and n give trivial decompositions and are always in this set).

Then the shortest grammar uses (p-1) symbols S_0 ... S_{p-1}, and each rule is of the described format, where to expand Si we have to choose $\delta_i = k_{i+1}-k_i$ letters before expanding the next symbol $S_{i+1}$. Thus the "size" of the grammar is about $\Sigma_{i=0}^{p-1} \delta_i 2^{\delta_i}$.

If you choose a family of partitions that keep the gaps $\delta_i$ small (for example bounded), you get a linear-sized grammar (there are a linear number of symbols and each rule is about the same size). If you allow them to grow slowly (for example around log(n)), you can still get a polynomial-sized grammar. Since it's not clear what kind of families of permutations you're thinking about, I can't get more precise than that.

-