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.
Deciding if a language induced by a Presburger formula is context-free
fl.formal languages;context free languages;decidability