Prefix-suffix duplication

García López de Lacalle, Jesús; Manea, Florin y Mitrana, Victor (2014). Prefix-suffix duplication. "Journal of computer and system sciences", v. 80 (n. 7); pp. 1254-1265. ISSN 0022-0000. https://doi.org/10.1016/j.jcss.2014.02.011.

Descripción

Título: Prefix-suffix duplication
Autor/es:
  • García López de Lacalle, Jesús
  • Manea, Florin
  • Mitrana, Victor
Tipo de Documento: Artículo
Título de Revista/Publicación: Journal of computer and system sciences
Fecha: Noviembre 2014
Volumen: 80
Materias:
Palabras Clave Informales: Bio-inspired operations ;Prefix-suffix duplication; Language theoretical properties;Prefix-suffix duplication distance ;Algorithms on words
Escuela: E.T.S.I. de Sistemas Informáticos (UPM)
Departamento: Matemática Aplicada a las Tecnologías de la Información y las Comunicaciones
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (5MB) | Vista Previa

Resumen

We consider a bio-inspired formal operation on words called prefix-suffix duplication which consists in the duplication of a prefix or suffix of a given word. The class of languages defined by the iterated application of the prefix-suffix 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 a 0(n2 logn) time and 0(n2 ) space recognition algorithm. Two algorithms are further proposed for computing the prefix-suffix duplication distance between two words, defined as the minimal number of prefix-suffix duplications applied to one of them in order to get the other one. The first algorithm runs in cubic time and uses quadratic space while the second one is more efficient, having 0(n2 logn) time complexity, but needs 0(n2 logn) space .

Más información

ID de Registro: 40305
Identificador DC: http://oa.upm.es/40305/
Identificador OAI: oai:oa.upm.es:40305
Identificador DOI: 10.1016/j.jcss.2014.02.011
URL Oficial: http://www.sciencedirect.com/science/article/pii/S0022000014000233
Depositado por: Memoria Investigacion
Depositado el: 26 May 2017 17:42
Ultima Modificación: 26 May 2017 17:42
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM