¿Progreso en el problema generalizado de la altura de las estrellas?

15

La altura de estrella (generalizada) de un idioma es la anidación mínima de estrellas de Kleene requerida para representar el idioma mediante una expresión regular extendida. Recuerde que una expresión regular extendida sobre un alfabeto finito A satisface lo siguiente:

(1) ,1 y a son expresiones regulares extendidas para todo aA

(2) Para todas las expresiones regulares extendidas E,F ; , , y son expresiones regulares extendidas
EFEFEEc

Una formulación del problema de altura de estrella generalizada es si hay un algoritmo para calcular la altura de estrella generalizada mínima. Con respecto a este problema, tengo algunas preguntas.

  1. ¿Ha habido algún progreso reciente (o interés de investigación) con respecto a este problema? Sé hace varios años que Pin Straubing y Thérien publicaron algunos artículos en esta área.

  2. El problema restringido de la altura de la estrella fue resuelto en 1988 por Hashiguchi, pero la versión generalizada (que yo sepa) aún está abierta. ¿Alguien tiene alguna intuición de por qué este podría ser el caso?

Un enlace que puede ser útil es el siguiente: starheight

matemáticas confusas
fuente
Sería útil una definición clara de 'expresión regular extendida "o un enlace. También los enlaces a los documentos citados ayudarían a desarrollar la pregunta
Suresh Venkat
2
@Suresh Dado un alfabeto finito A, las expresiones regulares extendidas se definen por: por cada a A son expresiones regulares extendidas. Además, unión, concatenación, complemento y estrella son expresiones regulares extendidas. Básicamente solo agregando complemento. Un enlace que puede ser útil es el siguiente: liafa.jussieu.fr/~jep/PDF/StarHeight.pdf,1,aaA
confusedmath
2
AFAIK, Pin mantiene su página web actualizada ( liafa.jussieu.fr/~jep/Problemes/starheight.html ), lo que significaría que no hay progreso.
Michaël Cadilhac
gracias: aún mejor sería incorporarlo en la pregunta.
Suresh Venkat
1
En los comentarios anteriores, "liafa.jussieu.fr" debería reemplazarse "www.liafa.univ-paris-diderot.fr". Edité el enlace en la pregunta, pero no pude editar los enlaces en los comentarios.
J.-E.

Respuestas:

9

Con respecto a su segunda pregunta, una explicación de por qué el problema generalizado de la altura de la estrella es menos accesible que el problema de la altura de la estrella es la siguiente: Ya el artículo seminal de Eggan en 1963 contenía idiomas de altura de la estrella (ordinaria) , para cada k 0 . Solo unos años más tarde, McNaughton y, de forma independiente, Déjean y Schützenberger, encontraron ejemplos sobre alfabetos binarios. Esto dejó en claro de qué se trata el problema ". Durante los años que siguieron, hubo un flujo más o menos constante de resultados publicados en el área del problema ordinario de la altura de la estrella. Esto dio un cuerpo cada vez mayor de ejemplos publicados, contraejemplos y fenómenos que rodean este problema.kk0

Por el contrario, después de unos cincuenta años, no sabemos si hay algún lenguaje regular de altura de estrella al menos dos. Por lo tanto, ni siquiera sabemos si es necesario un procedimiento de decisión después de todo. Esta "falta total de ejemplos" indica que es extremadamente difícil controlar este problema.

Hermann Gruber
fuente
¿Conoces alguna aplicación / área que se vería directamente afectada por el descubrimiento de un algoritmo real? (excepto los de un punto de vista puramente intelectual)
confusedmath
1
01
1
Es probable que la altura restringida de las estrellas se aplique pronto en un trabajo sobre los costos aproximados de los componentes en los sistemas de comunicación. (no hay referencia todavía lo siento)
Denis
7

Esta respuesta está dedicada a la memoria de Janusz (John) Antoni Brzozowski, quien falleció el 24 de octubre de 2019.

John es sin duda la persona que hizo tan famosos los problemas de altura de las estrellas. De hecho, en una conferencia en Santa Bárbara en diciembre de 1979, presentó una selección de seis problemas abiertos sobre los idiomas regulares y mencionó otros dos temas en la conclusión de su artículo [1]. Estos seis problemas abiertos fueron, en orden, la altura de la estrella, la altura restringida de la estrella, la complejidad del grupo, la eliminación de la estrella, la regularidad de las clases sin contar y la optimización de los códigos de prefijo. Los otros dos temas fueron el problema de la limitación y la jerarquía de profundidad de puntos.

En junio de 2015, durante una conferencia de un día en honor a su 80 cumpleaños , presenté dos artículos de encuesta que resumen el estado del arte en estas preguntas [2, 3]. En particular, encontrará en [2] información detallada sobre los problemas de altura de las estrellas.

[1] JA Brzozowski, Problemas abiertos sobre lenguajes regulares , en la teoría del lenguaje formal. Perspectivas y problemas abiertos, Actas de un simposio celebrado en Santa Bárbara, California, del 10 al 14 de diciembre de 1979 [, RV Book (ed.), Pp. 23–47, New York Etc .: Academic Press, una subsidiaria de Harcourt Brace Jovanovich, Editores. XIII, 454 p., 1980.

[2] J.-É. Pin, Problemas abiertos sobre idiomas regulares, 35 años después , Stavros Konstantinidis; Nelma Moreira; Rogério Reis; Jeffrey Shallit. El papel de la teoría en ciencias de la computación: ensayos dedicados a Janusz Brzozowski, World Scientific, 2017,

[3] J.-É. Pin, La jerarquía de profundidad de puntos, 45 años después . Stavros Konstantinidis; Nelma Moreira; Rogério Reis; Jeffrey Shallit. El papel de la teoría en informática: ensayos dedicados a Janusz Brzozowski, World Scientific, 2017.

J.-E. Alfiler
fuente
Gracias por compartir esto: acabo de enterarme de su respuesta de que falleció.
Hermann Gruber
2

La solución del problema restringido de altura estelar inspiró la rica teoría de las funciones de costo regular (por Colcombet), que a su vez ayudó a resolver otros problemas de capacidad de decisión y ofrece nuevas herramientas para atacar problemas abiertos. Esta teoría aún se está desarrollando y se extendió a palabras infinitas, árboles finitos, árboles infinitos, con su propio conjunto de resultados profundos y problemas abiertos. Aquí hay un artículo seminal de la teoría, y una bibliografía , del sitio web de Colcombet.

Entonces, aunque no es directamente una aplicación de altura de estrella generalizada, muestra que progresar en problemas aparentemente inútiles como la altura de estrella probablemente signifique una mejor comprensión de los idiomas regulares y arroje nuevos resultados en diferentes problemas.

Referencia: Thomas Colcombet. "La teoría de los monoides de estabilización y las funciones de costo regular". En: ICALP 2009

Denis
fuente