20
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$ Apr 1, 2011 at 20:35
  • $\begingroup$ 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. $\endgroup$ Apr 3, 2011 at 14:26

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jan 16, 2014 at 12:05
4
$\begingroup$

Recently, a criterion for the special case of deciding whether an integral polyhedron $A\cdot \vec{x} \ge \vec{b}$ is stratified has been developed here (Theorem 4.5):

Leroux, J., Penelle, V., & Sutre, G. (2014). The Context-Freeness Problem Is coNP-Complete for Flat Counter Systems. In Automated Technology for Verification and Analysis (pp. 248-263). Springer International Publishing.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jan 2, 2014 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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