Descripción
|
|
---|---|
We consider a bio-inspired formal operation on words called pre?x?su?x duplication which consists in the duplication of a pre?x or su?x of a given word. The class of languages de?ned by the iterated application of the pre?x?su?x duplication to a word is considered. We show that such a language is context-free if and only if the initial word contains just one letter. Moreover, every language in this class is semilinear and belongs to NL. We propose aO(n^2 logn) time and O(n^2) space recognition algorithm. Two algorithms are further proposed for computing the pre?x?su?x duplication distance between two words, de?ned as the minimal number of pre?x?su?x duplications applied to one of them in order to get the other one. The ?rst algorithm runs in cubic time and uses quadratic space while the second one is more e?cient, having O(n^2 logn) time complexity, but needs O(n^2 logn) space. | |
Internacional
|
Si |
JCR del ISI
|
Si |
Título de la revista
|
Journal of Computer And System Sciences |
ISSN
|
0022-0000 |
Factor de impacto JCR
|
1,091 |
Información de impacto
|
Datos JCR del año 2013 |
Volumen
|
80 |
DOI
|
10.1016/j.jcss.2014.02.011 |
Número de revista
|
7 |
Desde la página
|
1254 |
Hasta la página
|
1265 |
Mes
|
SIN MES |
Ranking
|
Q2 COMPUTER SCIENCE, THEORY & METHODS |