# Deciding if a language induced by a Presburger formula is context-free

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.

• 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. Jun 12, 2013 at 19:00
• @Michaël Cadilhac - thanks for the comment; I think you can change it to an answer. Jun 15, 2013 at 16:37
• 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! :) Aug 23, 2013 at 17:20