## Status of an open problem about semilinear sets

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.

-
 I've added the "arithmetic-progression" tag (even though you probably don't have only the r=1 case in mind). Perhaps even the "nt.number-theory" one might be appropriate (and would add the benefit of a substantial readership). – Thomas Sauvaget Apr 1 2011 at 20:35 Thanks. Certainly I don't really have the r=1 case in mind at all, since then the stratified condition means nothing. I have no idea whether this question would be interesting to number theorists, but I suppose it can't hurt to try putting the tag on. – Tara Brough Apr 3 2011 at 14:26