# 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 of 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 in n ? $\pi$ should depend on n, then. We want a permutation of {1...n} for every n, right ? –  mercio Jan 31 '11 at 10:10
Yes, polynomial in fixed $n$. $pi$ is fixed per language, so we don't want all permutations, just one fixed permutation (though all permutations will be interesting to me too). –  jerr18 Jan 31 '11 at 10:29
@chandok on second thought, yes, you are right. permutation for every (sufficiently large) n. –  jerr18 Jan 31 '11 at 10:31
An arbitrary grammar can be converted to Chomsky normal form with only a quadratic blowup, so no need to refer to Chomsky normal form if all you're interested is whether there's a polynomial size grammar or not. –  Yuval Filmus Jan 31 '11 at 16:09
cross-posted in MO: ttp://mathoverflow.net/questions/53884/can-a-polynomial-size-cfg-describe-the-fi‌​nite-language-w-piw-piw-is –  Yuval Filmus Jan 31 '11 at 18:36

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.

-
@chandok Thank you. If I understand correctly for $\pi(i) = (n-i+1+(-1)^i))$ you add 5 productions: $S \to \epsilon | abSab : \ \ a,b \in \{0,1\}$ ? This doesn't seem to depend on $n$, only on the width for which $\pi$ differs from $rev_n$ (and the palindromic case is constant size too - by definition $|w \pi(w)|=2n$)? Or am I missing something? –  jerr18 Feb 1 '11 at 9:07
@jerr18 : Yes this the kind of rule you get for this particular family of permutation. Although this grammar can give words of any even length (when you initially asked for a grammar describing the finite language for one fixed n) –  mercio Feb 1 '11 at 9:15
@chandok Yes you are right. My grammar gives arbitrary words of lengths multiple of 4. I may have not defined the question well enough - I assume I am working with fixed length words (and for my application I can allow "padding" if necessary). –  jerr18 Feb 1 '11 at 9:40
@chandok Thank you again, extremely helpful answer! Are you absolutely sure your answer completely rules out other tractable permutations? –  jerr18 Feb 1 '11 at 10:51
@jerr18 : I am not sure about what you mean about "other permutations". It doesn't make sense to ask if "the size of the grammar is polynomial in n" when n is fixed. So you absolutely need to talk about families of permutations, and there are obviously a lot of them. Some of which give "polynomial sized" grammars but it's not really an easy class of families to define. –  mercio Feb 1 '11 at 11:24