Is the following problem decidable?

Given $n$ and a Presburger arithmetic formula $\phi(x_1,x_2,\dots,x_n)$, determine whether the language $\{a_1^{i_1} \dots a_n^{i_n}:\phi(i_1,i_2,\dots,i_n)\}$ over alphabet $\{a_1, a_2, \dots, a_n\}$ is context-free.

For example, this covers asking if languages such as $\{a^i b^j c^{i+j}\}$, $\{a^i b^j c^i d^j\}$, $\{a^n b^n c^n\}$, $\{a^i b^j c^k: i\neq j, j \neq k, i \neq k\}$ are context-free.

  • 3
    $\begingroup$ This is equivalent to the question mathoverflow.net/questions/60288/… ; it is however more than two-year old and asked on a different SE site. As for the question, I believe it is still open. $\endgroup$ Jun 12, 2013 at 19:00
  • $\begingroup$ @Michaël Cadilhac - thanks for the comment; I think you can change it to an answer. $\endgroup$
    – sdcvvc
    Jun 15, 2013 at 16:37
  • 2
    $\begingroup$ I'd rather not; "still open" does not answer your question and would make the post disappear from the unanswered questions list. Let's wait for someone having some more constructive comments than mine! :) $\endgroup$ Aug 23, 2013 at 17:20


Your Answer

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