En su libro "The Mathematical Theory of Context-Free Languages" (1966), Ginsburg menciona el siguiente problema abierto:
Find a decision procedure for determining if an arbitrary semilinear set
is a finite union of linear sets, each with stratified periods.¿Alguien sabe si se ha avanzado algo al respecto? He buscado, pero no he encontrado ninguna información. Sí he encontrado que al menos uno de los otros problemas abiertos mencionados por Ginsburg se resolvió ya en la década de 1960.
En caso de que ya se haya hecho, pero utilizando una terminología diferente, he aquí las definiciones de los términos del problema:
A conjunto lineal es un conjunto de tuplas de enteros no negativos de la forma $L = \{c + \sum_{i=1}^n \alpha_i p_i \mid \alpha_i\in \mathbb{N}_0\}$ donde $\mathbb{N}_0$ denota los enteros no negativos y $c,p_1,\ldots,p_n$ son elementos fijos de $\mathbb{N}_0^r$ . En conjunto de periodos de $L$ es $P = \{p_1,\ldots,p_n\}$ . (El conjunto de períodos no está determinado unívocamente).
A conjunto semilineal es la unión de un número finito de conjuntos lineales.
Para $p\in\mathbb{N}_0^r$ denotamos el $i$ -enésimo componente de $p$ por $p(i)$ . Un subconjunto $P$ de $\mathbb{N}_0^r$ es estratificado si cumple las siguientes condiciones:
-
cada $p\in P$ tiene como máximo dos componentes distintas de cero, y
-
no existen $i<j<k<l$ y $p,q\in P$ tal que $p(i), p(k), q(j), q(l)$ son todos distintos de cero.
He utilizado la etiqueta lenguajes-formales porque mi interés en este problema proviene de la relación entre estos conjuntos y los lenguajes libres de contexto acotados (Teorema 5.4.2 del libro de Ginsburg).
EDIT: Si se te ocurre alguna etiqueta que pueda ayudar a que esta pregunta llegue a las personas adecuadas, por favor, añádela.
