Status of an open problem about semilinear sets

2011-04-01T13:16:40Z

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 - MathOverflow

Status of an open problem about semilinear sets