%0 Conference Paper
%A Gil Rubio, Francisco Javier
%A Mitrana, Victor
%A Dumitran, Marius
%A Manea, Florin
%B 19th International Conference, CIAA 2014 Giessen, Germany, July 30 – August 2, 2014 : Proceedings
%C Giessen, Alemania
%D 2014
%F upm:41500
%I Springer
%P 176-187
%R 10.1007/978-3-319-08846-4_13
%T Bounded prefix-suffix duplication
%U https://oa.upm.es/41500/
%V 8587
%X We consider a restricted variant of the prefix-suffix duplication operation, called bounded prefix-suffix duplication. It consists in the iterative duplication of a prefix or suffix, whose length is bounded by a constant, of a given word. We give a sufficient condition for the closure under bounded prefix-suffix duplication of a class of languages. Consequently, the class of regular languages is closed under bounded prefix-suffix duplication; furthermore, we propose an algorithm deciding whether a regular language is a finite k-prefix-suffix duplication language. An efficient algorithm solving the membership problem for the k-prefix-suffix duplication of a language is also presented. Finally, we define the k-prefix-suffix duplication distance between two words, extend it to languages and show how it can be computed for regular languages.