%I Springer
%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.
%A Francisco Javier Gil Rubio
%A Victor Mitrana
%A Marius Dumitran
%A Florin Manea
%C Cham (Suiza)
%R 10.1007/978-3-319-08846-4_13
%P 176-187
%B Implementation and application of automata : 19th International Conference, CIAA 2014 Giessen, Germany, July 30 – August 2, 2014 : Proceedings
%T Bounded prefix-suffix duplication
%V 8587
%L upm41500
%D 2014