<p>Is the following problem decidable?</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2013-06-15T16:37:08.997Z
@Michaël Cadilhac - thanks for the comment; I think you can change it to an answer.
sdcvvc
CC BY-SA 3.0
2013-08-23T17:20:58.923Z
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! :)
Michaël Cadilhac
CC BY-SA 3.0
2013-06-12T19:00:03.797Z
This is equivalent to the question http://mathoverflow.net/questions/60288/status-of-an-open-problem-about-semilinear-sets ; 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.
Michaël Cadilhac
<fl.formal-languages><context-free-languages><decidability>
Deciding if a language induced by a Presburger formula is context-free
sdcvvc
# Deciding if a language induced by a Presburger formula is context-free

(Asked by: username_0 on 2013-06-11)

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.

**Tags:** fl.formal-languages, context-free-languages, decidability

> **Comments:**
> **username_1**: This is equivalent to the question http://mathoverflow.net/questions/60288/status-of-an-open-problem-about-semilinear-sets ; 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.  
> **username_0**: @username_1 - thanks for the comment; I think you can change it to an answer.  
> **username_1**: 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! :)  

---

## 0 answers

