Texto completo
Vista Previa |
PDF (Portable Document Format)
- Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (5MB) | Vista Previa |
Prefix-suffix duplication
Cita
García López de Lacalle, Jesús 
ORCID: https://orcid.org/0000-0003-1218-396X, Manea, Florin and Mitrana, Victor ORCID: https://orcid.org/0000-0002-1457-8933
(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.
ORCID: https://orcid.org/0000-0003-1218-396X, Manea, Florin and Mitrana, Victor ORCID: https://orcid.org/0000-0002-1457-8933
(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: |
|
| Tipo de Documento: | Artículo |
| Título de Revista/Publicación: | Journal of computer and system sciences |
| Fecha: | Noviembre 2014 |
| ISSN: | 0022-0000 |
| Volumen: | 80 |
| Número: | 7 |
| Materias: | |
| ODS: | |
| 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 |
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: | https://oa.upm.es/40305/ |
| Identificador OAI: | oai:oa.upm.es:40305 |
| URL Portal Científico: | https://portalcientifico.upm.es/es/ipublic/item/9438760 |
| Identificador DOI: | 10.1016/j.jcss.2014.02.011 |
| URL Oficial: | http://www.sciencedirect.com/science/article/pii/S... |
| Depositado por: | Memoria Investigacion |
| Depositado el: | 26 May 2017 17:42 |
| Ultima Modificación: | 12 Nov 2025 00:00 |
Acciones
- Estadísticas
- Exportar cita
- Editar (sólo personal del Archivo)
