Kuratowski Algebras Generated by Factor-, Subword-, and Suffix-Free Languages - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

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

Matúš Palmovský
  • Fonction : Auteur
  • PersonId : 1024593
Juraj Šebej
  • Fonction : Auteur
  • PersonId : 1022721

Résumé

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.
Fichier principal
Vignette du fichier
440206_1_En_15_Chapter.pdf (260.26 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01657013 , version 1 (06-12-2017)

Licence

Paternité

Identifiants

Citer

Jozef Jirásek Jr., Matúš Palmovský, Juraj Šebej. Kuratowski Algebras Generated by Factor-, Subword-, and Suffix-Free Languages. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. pp.189-201, ⟨10.1007/978-3-319-60252-3_15⟩. ⟨hal-01657013⟩
32 Consultations
83 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More