1
$\begingroup$

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.

  • 0
    Polynomial in n ? $\pi$ should depend on n, then. We want a permutation of {1...n} for every n, right ?2011-01-31
  • 0
    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).2011-01-31
  • 0
    @chandok on second thought, yes, you are right. permutation for every (sufficiently large) n.2011-01-31
  • 0
    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.2011-01-31
  • 0
    If you allow all permutations then there's a very simple stack automaton that does the trick (in polynomial size).2011-01-31
  • 0
    Jerr18, the statement of your question is ambiguous because we don't know if $\pi$ is fixed for each language or not, whether it varies with the language, or is fixed, or depends on $n$ or not, etc. Could you kindly edit your question to make it precise?2011-01-31
  • 0
    Please indicate that this is a cross-post with MO. I will repost my answer from there to here.2011-01-31
  • 1
    cross-posted in MO: ttp://mathoverflow.net/questions/53884/can-a-polynomial-size-cfg-describe-the-finite-language-w-piw-piw-is2011-01-31
  • 0
    @Yuval Filmus, it doesn't even take a stack automaton. There's a simple DFSM in $O(n^2)$ size.2011-01-31
  • 0
    @JDH Thank you. I edited the question.2011-02-01
  • 0
    I wonder whether it's possible to prove by the pigeon-hole principle that $\lim_{n\to\infty}$ the proportion of permutations $\pi$ for which the corresponding language can be matched by a polynomial CFG tends to zero, because there's a polynomial number of CFGs meeting any polynomial bound but a factorial number of permutations.2011-02-01
  • 0
    @Peter I am trying to identify the tractable cases, even if they are quite rare.2011-02-01

1 Answers 1

2

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.

  • 0
    @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?2011-02-01
  • 0
    @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)2011-02-01
  • 0
    @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).2011-02-01
  • 0
    @chandok Thank you again, extremely helpful answer! Are you absolutely sure your answer completely rules out other tractable permutations?2011-02-01
  • 0
    @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.2011-02-01
  • 0
    @chandok Thank you. So you unconditionally rule out $id_n$ (word repetition)?2011-02-01
  • 0
    @jerr18 : yes, there is no way to avoid enumerating all 2^n words for this particular family id_n of permutations2011-02-01
  • 0
    Appears your method would polynomially scale to large alphabets.2011-02-02