Kuratowski Algebras Generated by Factor-, Subword-, and Suffix-Free Languages

Abstract : We study Kuratowski algebras generated by suffix-, factor-, and subword-free languages under the operations of star and complementation. We examine 12 possible algebras, and for each of them, we provide an answer to the question whether or not it can be generated by a suffix-, factor-, or subword-free language. In each case when an algebra can be generated by such a language, we show that this language may be taken to be regular, and we compute upper bounds on the state complexities of all the generated languages. Finally, we find generators that maximize these complexities.
Type de document :
Communication dans un congrès
Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.189-201, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_15〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01657013
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 décembre 2017 - 11:44:33
Dernière modification le : mercredi 6 décembre 2017 - 13:46:16

Fichier

 Accès restreint
Fichier visible le : 2020-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Jozef Jirásek Jr., Matúš Palmovský, Juraj Šebej. Kuratowski Algebras Generated by Factor-, Subword-, and Suffix-Free Languages. Giovanni Pighizzini; Cezar Câmpeanu. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10316, pp.189-201, 2017, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-60252-3_15〉. 〈hal-01657013〉

Partager

Métriques

Consultations de la notice

20