%0 Conference Proceedings
%T Kuratowski Algebras Generated by Factor-, Subword-, and Suffix-Free Languages
%+ Slovak Academy of Sciences (SAS)
%+ P.J. Safarik University
%A Jirásek Jr., Jozef
%A Palmovský, Matúš
%A Šebej, Juraj
%Z Part 2: Contributed Papers
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 19th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Milano, Italy
%Y Giovanni Pighizzini
%Y Cezar Câmpeanu
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-10316
%P 189-201
%8 2017-07-03
%D 2017
%R 10.1007/978-3-319-60252-3_15
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01657013/document
%2 https://inria.hal.science/hal-01657013/file/440206_1_En_15_Chapter.pdf
%L hal-01657013
%U https://inria.hal.science/hal-01657013
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-10316