Memorias de investigación
Artículos en revistas:
Prefix-suffix duplication
Año:2014
Áreas de investigación
  • Ciencias de la computación y tecnología informática
Datos
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
Esta actividad pertenece a memorias de investigación
Participantes
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Departamento: Matemática Aplicada a Las Tecnologías de la Información y Las Comunicaciones