TY  - CONF
TI  - Bounded prefix-suffix duplication
SP  - 176
AV  - public
N2  - 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.
CY  - Cham (Suiza)
VL  - 8587
Y1  - 2014///
M2  - Giessen, Alemania
EP  - 187
PB  - Springer
T2  - 19th International Conference, CIAA 2014 Giessen, Germany, July 30 ? August 2, 2014 : Proceedings
UR  - https://link.springer.com/chapter/10.1007/978-3-319-08846-4_13
SN  - 978-3-319-08845-7
ID  - upm41500
A1  - Gil Rubio, Francisco Javier
A1  - Mitrana, Victor
A1  - Dumitran, Marius
A1  - Manea, Florin
ER  -