Problema generalizado de la altura de las estrellas

El problema generalizado de la altura de las estrellas en la teoría de lenguajes formales es la cuestión abierta de si todos los lenguajes regulares pueden expresarse utilizando expresiones regulares generalizadas con una profundidad de anidamiento limitada de estrellas de Kleene . Aquí, las expresiones regulares generalizadas se definen como expresiones regulares , pero tienen un operador de complemento incorporado. Para un lenguaje regular, su altura de estrella generalizada se define como la profundidad de anidamiento mínima de estrellas de Kleene necesaria para describir el lenguaje por medio de una expresión regular generalizada, de ahí el nombre del problema.

Más específicamente, es una pregunta abierta si se requiere una profundidad de anidamiento de más de 1 y, de ser así, si existe un algoritmo para determinar la altura de estrella mínima requerida. ^[1]

Los lenguajes regulares de altura de estrella 0 también se conocen como lenguajes sin estrellas . El teorema de Schützenberger proporciona una caracterización algebraica de los lenguajes sin estrellas mediante monoides sintácticos aperiódicos . En particular, los lenguajes sin estrellas son una subclase decidible propia de los lenguajes regulares.

• Secciones del artículo Altura de la estrella y teorema de Eggan del artículo Altura de la estrella
• Problema de altura de las estrellas

• Janusz A. Brzozowski (1980). "Problemas abiertos sobre lenguajes regulares". En Ronald V. Book (ed.). Teoría del lenguaje formal: perspectivas y problemas abiertos . Academic Press. págs. 23–47.
• Wolfgang Thomas (1981). "Observación sobre el problema de la altura de las estrellas". Ciencias Informáticas Teóricas . 13 (2): 231–237. doi : 10.1016/0304-3975(81)90041-4 . MR  0594062.
• Jean-Eric Pin; Howard Straubing; Denis Thérien (1992). "Algunos resultados sobre el problema generalizado de la altura de las estrellas" (PDF) . Información y Computación . 101 (2): 219–250. doi :10.1016/0890-5401(92)90063-L.
• 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.Zbl 1188.68177  .
• Marcel-Paul Schützenberger (1965). "Sobre monoides finitos que tienen sólo subgrupos triviales". Información y Control . 8 (2): 190–194. doi : 10.1016/S0019-9958(65)90108-7 . Zbl  0131.02001.

• Jean-Eric Pin: El problema de la altura de las estrellas