Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
Prefix-suffix duplication
Year:2014
Research Areas
  • Information technology and adata processing
Information
Abstract
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.
International
Si
JCR
Si
Title
Journal of Computer And System Sciences
ISBN
0022-0000
Impact factor JCR
1,091
Impact info
Datos JCR del año 2013
Volume
80
10.1016/j.jcss.2014.02.011
Journal number
7
From page
1254
To page
1265
Month
SIN MES
Ranking
Q2 COMPUTER SCIENCE, THEORY & METHODS
Participants
  • Autor: Jesus Garcia Lopez de Lacalle (UPM)
  • Autor: Victor Mitrana (UPM)
Research Group, Departaments and Institutes related
  • Creador: Departamento: Matemática Aplicada a Las Tecnologías de la Información y Las Comunicaciones
S2i 2020 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)