Full text
|
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (5MB) | Preview |
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.
Title: | Prefix-suffix duplication |
---|---|
Author/s: |
|
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 |
|
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (5MB) | Preview |
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 .
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 |