"Teorema de Kuratowski del complemento de cierre" para lenguajes formales

Question

Un famoso teorema/enigma/problema de topología consiste en demostrar que, dado cualquier subconjunto de un espacio topológico, se pueden obtener como máximo 14 conjuntos distintos a partir de él mediante el uso iterativo de las operaciones cierre y complemento. (Véase el artículo de Wikipedia sobre el Problema del complemento de cierre de Kuratowski .)

En el ámbito de los lenguajes formales, me parece que se puede argumentar que el Operador estrella de Kleene puede considerarse un tipo de cierre. Y la complementación es la complementación.

Así que tenía curiosidad por la siguiente pregunta: Dado un alfabeto $\Sigma$ y el lenguaje $L \subseteq \Sigma^*$ ¿cuál es el número máximo de lenguas diferentes que se pueden obtener a partir de $L$ aplicando iterativamente los operadores estrella de Kleene y de complementación? También sería instructivo un ejemplo de un lenguaje para el que se alcance este máximo.

Answer 1

Dado que la estrella de Kleene es una operador de cierre combinándolo con la complementación puede producir como máximo 14 lenguajes distintos (P. C. Hammer. Teorema de cierre de Kuratowski, Nieuw Arch. Wisk ., 8(2):74-80, 1960).

En la sección 4.1 del siguiente documento, el autor afirma sin pruebas que $L=\{a,aab,bbb\}$ genera el máximo donde $\Sigma=\{a,b\}$ .

D. Peleg. Un fenómeno generalizado de cierre y complemento. Matemáticas discretas ., 50:285-293, 1984. http://dx.doi.org/10.1016/0012-365X(84)90055-4

Los siguientes documentos abordan temas similares.

J. Brzozowski, E. Grant y J. Shallit. Cierres en lenguajes formales: Concatenación, separación y algoritmos. Comp. Investigación - CORR abs/0901.3. arXiv:1109.1227 [math.GN], arXiv.org, 2009. http://arxiv.org/abs/0901.3763

J. Brzozowski, E. Grant y J. Shallit. Closures in formal languages and Kuratowski's theorem. Intl. J. Found. Comp. Sci. , 22:301-321, 2011. http://dx.doi.org/10.1142/S0129054111008052

J. Brzozowski, G. Jirásková y C. Zou. Quotient complexity of closed languages. Teoría Comput. Syst. , 54(2):277-292, 2014. ISSN 1432-4350. http://dx.doi.org/10.1007/s00224-013-9515-7

É. Charlier, M. Domaratzki, T. Harju y J. Shallit. Órbitas finitas de operaciones lingüísticas. Language and Automata Theory and Applications, Actas de la 5ª Conferencia Internacional, páginas 204-215, 2011. http://dx.doi.org/10.1007/978-3-642-21254-3_15

É. Charlier, M. Domaratzki, T. Harju y J. Shallit. Composición y órbitas de operaciones lingüísticas: Finiteness and upper bounds. Intl. J. Comp. Math. , páginas 1-26, 2012. http://dx.doi.org/10.1080/00207160.2012.681305

Š. Holub y J. Kortelainen. Sobre particiones que separan palabras. Intl. J. Algebra Comp. , 21(8):1305-1316, 2011. http://dx.doi.org/10.1142/S0218196711006650

J. Jirásek, M. Palmovský y J. Šebej. Kuratowski algebras generated by factor-, subword-, and suffix-free languages. International Conference on Descriptional Complexity of Formal Systems, páginas 189-201, 2017. http://dx.doi.org/10.1007/978-3-319-60252-3_15

J. Jirásek y Juraj Šebej. Álgebras de Kuratowski generadas por lenguajes sin prefijo. Implementation and Application of Automata, CIAA 2016, páginas 150-162, 2016. http://dx.doi.org/10.1007/978-3-319-40946-7_13