Problema generalizado de la altura de las estrellas

El problema de la altura de estrella generalizada en la teoría del lenguaje formal plantea la cuestión abierta de si todos los lenguajes regulares pueden expresarse mediante expresiones regulares generalizadas con una profundidad de anidamiento limitada de estrellas de Kleene . Aquí, las expresiones regulares generalizadas se definen como expresiones regulares , pero incorporan un operador de complemento. 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 mediante una expresión regular generalizada; de ahí el nombre del problema.

Más concretamente, es una cuestión abierta si se requiere una profundidad de anidamiento superior a 1 y, en caso afirmativo, si existe un algoritmo para determinar la altura mínima requerida de la estrella. ^{[ 1 ]}

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

• El teorema de Eggan y las secciones de altura de estrella generalizada del artículo sobre la 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. pp. 23–47 . 
• Wolfgang Thomas (1981). "Observación sobre el problema de la altura de la estrella" . Theoretical Computer Science . 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) . Information and Computation . 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 solo tienen subgrupos triviales" . Information and 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