Prefix-suffix duplication

García López de Lacalle, Jesús and Manea, Florin and 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.

Description

Title: Prefix-suffix duplication
Author/s:
  • García López de Lacalle, Jesús
  • Manea, Florin
  • Mitrana, Victor
Item Type: Article
Título de Revista/Publicación: Journal of computer and system sciences
Date: November 2014
ISSN: 0022-0000
Volume: 80
Subjects:
Freetext Keywords: Bio-inspired operations ;Prefix-suffix duplication; Language theoretical properties;Prefix-suffix duplication distance ;Algorithms on words
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Matemática Aplicada a las Tecnologías de la Información y las Comunicaciones
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (5MB) | Preview

Abstract

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 .

More information

Item ID: 40305
DC Identifier: http://oa.upm.es/40305/
OAI Identifier: oai:oa.upm.es:40305
DOI: 10.1016/j.jcss.2014.02.011
Official URL: http://www.sciencedirect.com/science/article/pii/S0022000014000233
Deposited by: Memoria Investigacion
Deposited on: 26 May 2017 17:42
Last Modified: 26 May 2017 17:42
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM