In his book "The Mathematical Theory of Context-Free Languages" (1966), Ginsburg mentioned the following open problem:



```

Find a decision procedure for determining if an arbitrary semilinear set   
is a finite union of linear sets, each with stratified periods.

```

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.


In case this has been done, but using different terminology, here are the definitions of the terms in the problem:


A *linear set* 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 *set of periods* of $L$ is $P = \{p\_1,\ldots,p\_n\}$. (The set of periods is not uniquely determined.) 


A *semilinear set* is a union of finitely many linear sets.


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 *stratified* if it satisfies the following conditions:


* each $p\in P$ has at most two non-zero components, and
* there do not exist $i<j<k<l$ and $p,q\in P$ such that $p(i), p(k), q(j), q(l)$ are all non-zero.


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). 


EDIT: If you can think of any tags that might help this question come to the attention of the right people, please add them.



Status of an open problem about semilinear sets
See the paper below.


"On the open problem of Ginsburg concerning semilinear sets and related problems" by Ibarra and Seki, TCS 501, pp.11-19, 2013


link: <http://dl.acm.org/citation.cfm?id=2527409>


Hope it can help.


