Status of an open problem about semilinear sets - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T08:47:45Z http://mathoverflow.net/feeds/question/60288 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/60288/status-of-an-open-problem-about-semilinear-sets Status of an open problem about semilinear sets Tara Brough 2011-04-01T13:16:40Z 2011-04-18T11:56:58Z <p>In his book "The Mathematical Theory of Context-Free Languages" (1966), Ginsburg mentioned the following open problem:</p> <pre> Find a decision procedure for determining if an arbitrary semilinear set is a finite union of linear sets, each with stratified periods. </pre> <p>Does anyone know if any progress has been made on this? I have searched, but not found any information. I did find that at least one of the other open problems mentioned by Ginsburg was solved already in the 1960s.</p> <p>In case this has been done, but using different terminology, here are the definitions of the terms in the problem:</p> <p>A <em>linear set</em> is a set of tuples of nonnegative integers of the form $L = \{c + \sum_{i=1}^n \alpha_i p_i \mid \alpha_i\in \mathbb{N}_0\}$, where $\mathbb{N}_0$ denotes the nonnegative integers and $c,p_1,\ldots,p_n$ are fixed elements of $\mathbb{N}_0^r$. The <em>set of periods</em> of $L$ is $P = \{p_1,\ldots,p_n\}$. (The set of periods is not uniquely determined.) </p> <p>A <em>semilinear set</em> is a union of finitely many linear sets.</p> <p>For $p\in\mathbb{N}_0^r$, we denote the $i$-th component of $p$ by $p(i)$. A subset $P$ of $\mathbb{N}_0^r$ is <em>stratified</em> if it satisfies the following conditions:</p> <ul> <li><p>each $p\in P$ has at most two non-zero components, and</p></li> <li><p>there do not exist <code>$i&lt;j&lt;k&lt;l$</code> and $p,q\in P$ such that $p(i), p(k), q(j), q(l)$ are all non-zero.</p></li> </ul> <p>I have used the formal-languages tag because my interest in this problem comes from the relationship between these sets and bounded context-free languages (Theorem 5.4.2 in Ginsburg's book). </p> <p>EDIT: If you can think of any tags that might help this question come to the attention of the right people, please add them.</p>