Problema de altura de las estrellas

Problema en la teoría del lenguaje formal

El problema de la altura de las estrellas en la teoría de lenguajes formales es la cuestión de si todos los lenguajes regulares pueden expresarse utilizando expresiones regulares de altura de estrella limitada , es decir, con una profundidad de anidamiento limitada de estrellas de Kleene . En concreto, ¿es siempre suficiente una profundidad de anidamiento de uno? Si no, ¿existe un algoritmo para determinar cuántas se requieren? El problema fue introducido por primera vez por Eggan en 1963. ^[1]

Familias de lenguajes regulares con altura de estrella ilimitada

La primera pregunta fue respondida negativamente cuando en 1963 Eggan dio ejemplos de lenguajes regulares con altura de estrella n para cada n . Aquí, la altura de estrella h ( L ) de un lenguaje regular L se define como la altura de estrella mínima entre todas las expresiones regulares que representan L . Los primeros lenguajes encontrados por Eggan se describen a continuación, mediante la presentación de una expresión regular para cada lenguaje:

${\displaystyle {\begin{alignedat}{2}e_{1}&=a_{1}^{*}\\e_{2}&=\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\\e_{3}&=\left(\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\left(a_{4}^{*}a_{5}^{*}a_{6}\right)^{*}a_{7}\right)^{*}\\e_{4}&=\left(\left(\left(a_{1}^{*}a_{2}^{*}a_{3}\right)^{*}\left(a_{4}^{*}a_{5}^{*}a_{6}\right)^{*}a_{7}\right)^{*}\left(\left(a_{8}^{*}a_{9}^{*}a_{10}\right)^{*}\left(a_{11}^{*}a_{12}^{*}a_{13}\right)^{*}a_{14}\right)^{*}a_{15}\right)^{*}\end{alignedat}}}$

El principio de construcción de estas expresiones es que la expresión se obtiene concatenando dos copias de , renombrando apropiadamente las letras de la segunda copia usando nuevos símbolos del alfabeto, concatenando el resultado con otro nuevo símbolo del alfabeto y luego rodeando la expresión resultante con una estrella de Kleene. La parte restante, más difícil, es demostrar que para no existe una expresión regular equivalente de altura de estrella menor que n ; se da una prueba en Eggan (1963). ${\displaystyle e_{n+1}}$ ${\displaystyle e_{n}}$ ${\displaystyle e_{n}}$

Sin embargo, los ejemplos de Eggan utilizan un alfabeto grande , de tamaño 2 ⁿ -1 para el lenguaje con altura de estrella n . Por lo tanto, se preguntó si también podemos encontrar ejemplos sobre alfabetos binarios. Esto fue demostrado poco después por Dejean y Schützenberger en 1966. ^[2] Sus ejemplos pueden describirse mediante una familia definida inductivamente de expresiones regulares sobre el alfabeto binario de la siguiente manera –cf. Salomaa (1981): ${\displaystyle \{a,b\}}$

${\displaystyle {\begin{alignedat}{2}e_{1}&=(ab)^{*}\\e_{2}&=\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}\\e_{3}&=\left(aaaa\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}bbbb\left(aa(ab)^{*}bb(ab)^{*}\right)^{*}\right)^{*}\\\,&\cdots \\e_{n+1}&=(\,\underbrace {a\cdots a} _{2^{n}}\,\cdot \,e_{n}\,\cdot \,\underbrace {b\cdots b} _{2^{n}}\,\cdot \,e_{n}\,)^{*}\end{alignedat}}}$

Nuevamente, se necesita una prueba rigurosa del hecho de que no admite una expresión regular equivalente de menor altura de estrella. Las pruebas las proporcionan Dejean y Schützenberger (1966) y Salomaa (1981). ${\displaystyle e_{n}}$

Calcular la altura de estrella de los lenguajes regulares

En cambio, la segunda cuestión resultó ser mucho más difícil, y se convirtió en un famoso problema abierto en la teoría del lenguaje formal durante más de dos décadas. ^[3] Durante años, hubo pocos avances. Los lenguajes de grupo puro fueron la primera familia interesante de lenguajes regulares para los que se demostró que el problema de la altura de estrella era decidible . ^[4] Pero el problema general permaneció abierto durante más de 25 años hasta que fue resuelto por Hashiguchi , quien en 1988 publicó un algoritmo para determinar la altura de estrella de cualquier lenguaje regular. ^[5] El algoritmo no era en absoluto práctico, ya que no tenía una complejidad elemental . Para ilustrar el inmenso consumo de recursos de ese algoritmo, Lombardy y Sakarovitch (2002) dan algunos números reales:

[El procedimiento descrito por Hashiguchi] conduce a cálculos que son, con mucho, imposibles, incluso para ejemplos muy pequeños. Por ejemplo, si L es aceptado por un autómata de 4 estados con una complejidad de bucle de 3 (y con un pequeño monoide de transición de 10 elementos), entonces un minorante muy bajo del número de lenguajes que se deben probar con L para determinar su igualdad es: ${\displaystyle \left(10^{10^{10}}\right)^{\left(10^{10^{10}}\right)^{\left(10^{10^{10}}\right)}}.}$

—  S. Lombardy y J. Sakarovitch, Altura estelar de los lenguajes reversibles y los autómatas universales , LATIN 2002

Obsérvese que solo el número tiene 10 mil millones de ceros cuando se escribe en notación decimal , y ya es mucho mayor que el número de átomos en el universo observable . ${\displaystyle 10^{10^{10}}}$

En 2005, Kirsten ideó un algoritmo mucho más eficiente que el procedimiento de Hashiguchi. ^[6] Este algoritmo funciona, para un autómata finito no determinista dado como entrada, dentro de un espacio exponencial doble . Sin embargo, los requisitos de recursos de este algoritmo aún exceden en gran medida los márgenes de lo que se considera prácticamente factible.

Este algoritmo fue optimizado y generalizado a árboles por Colcombet y Löding en 2008, ^[7] como parte de la teoría de funciones de costo regulares. Fue implementado en 2017 en el conjunto de herramientas Stamina. ^[8]

Véase también

• Problema generalizado de altura de estrella
• Algoritmo de Kleene : calcula una expresión regular (generalmente de una altura de estrella no mínima) para un lenguaje dado por un autómata finito determinista.

Notas

1. Egan 1963.
2. Dejean y Schützenberger 1966.
3. Brzozowski 1980.
4. McNaughton 1967.
5. Hashiguchi 1988.
6. Kirsten 2005.
7. Colcombet y Löding 2008.
8. Fijalkow y otros. 2017.

Referencias

• Brzozowski, Janusz A. (1980). "Problemas abiertos sobre lenguajes regulares". En Book, Ronald V. (ed.). Teoría del lenguaje formal: perspectivas y problemas abiertos . Nueva York: Academic Press. pp. 23–47. ISBN 978-0-12-115350-2.(versión informe técnico)
• Colcombet, Thomas; Löding, Christof (2008). "La profundidad de anidación del cálculo μ disyuntivo para lenguajes arbóreos y el problema de la limitación". Lógica informática . Apuntes de clase en informática. Vol. 5213. págs. 416–430. doi :10.1007/978-3-540-87531-4_30. ISBN 978-3-540-87530-7. ISSN  0302-9743.
• Dejean, Françoise; Schützenberger, Marcel-Paul (1966). "Sobre una cuestión de Eggan". Información y Control . 9 (1): 23–25. doi :10.1016/S0019-9958(66)90083-0.
• Eggan, Lawrence C. (1963). "Gráficos de transición y la altura de la estrella de eventos regulares". Michigan Mathematical Journal . 10 (4): 385–397. doi : 10.1307/mmj/1028998975 . Zbl  0173.01504.
• McNaughton, Robert (1967). "La complejidad de bucles de eventos de grupo puro". Información y control . 11 (1–2): 167–176. doi :10.1016/S0019-9958(67)90481-0.
• Salomaa, Arto (1981). Joyas de la teoría del lenguaje formal . Melbourne: Pitman Publishing. ISBN 978-0-273-08522-5.Zbl 0487.68063  .

Lectura adicional

• Hashiguchi, Kosaburo (1982). "Lenguajes regulares de altura de estrella uno". Información y Control . 53 (2): 199–210. doi :10.1016/S0019-9958(82)91028-2.
• Hashiguchi, Kosaburo (1988). "Algoritmos para determinar la altura relativa de las estrellas y la altura de las estrellas". Información y computación . 78 (2): 124–169. doi : 10.1016/0890-5401(88)90033-8 .
• Lombardy, Sylvain; Sakarovitch, Jacques (2002). "Altura estelar de lenguajes reversibles y autómatas universales". LATIN 2002: Informática teórica (PDF) . Apuntes de informática. Vol. 2286. Springer. págs. 76–90. doi :10.1007/3-540-45995-2_12. ISBN 978-3-540-43400-9.
• Kirsten, Daniel (2005). "Autómatas del desierto a distancia y el problema de la altura de las estrellas". RAIRO - Informática teórica y aplicaciones . 39 (3): 455–509. doi :10.1051/ita:2005027.
• Sakarovitch, Jacques (2009). Elementos de la teoría de autómatas . Traducido del francés por Reuben Thomas. Cambridge: Cambridge University Press . ISBN 978-0-521-84425-3.Zbl1188.68177  .​
• Fijalkow, Nathanaël; Gimbert, Hugo; Kelmendi, Edón; Kuperberg, Denis (2017). Carayol, Arnaud; Nicaud, Cyril (eds.). Resistencia: monoides de estabilización en la teoría de los autómatas. CIAA. Cham: Editorial Internacional Springer. págs. 101-112. doi :10.1007/978-3-319-60134-2_9. ISBN 978-3-319-60134-2.