Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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 '11 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 '11 at 14:26
add comment

2 Answers

up vote 4 down vote accepted

See the paper below.

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

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

Hope it can help.

share|improve this answer
    
Thanks very much, this is exactly the sort of thing I was looking for. This not only confirms that the problem is (at least as far as the authors of the paper are aware) still open, but gives a potential alternative approach to determining whether or not it is decidable. –  Tara Brough Jan 16 at 12:05
add comment

Look at this paper, it may help:

Every semilinear set is a finite union of disjoint linear sets by: Ryuichi Ito

link: http://www.sciencedirect.com/science/article/pii/S0022000069800140

share|improve this answer
    
Thanks, I haven't had time to look at it in detail yet, but since it doesn't seem to say anything about stratification, I'm not sure how helpful it will be. –  Tara Brough Jan 2 at 21:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.