Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
Bounded Prefix-Suffix Duplication: Language Theoretic and Algorithmic Results
Año:2015
Áreas de investigación
  • Ciencias de la computación y tecnología informática
Datos
Descripción
We consider a restricted variant of the prefix-suffix duplication operation, called bounded prefix-suffix duplication. It consists in the iterative duplication of a length-bounded prefix or suffix of a given word. We give a sufficient condition for the closure of a class of languages under bounded prefix-suffix duplication. Consequently, we get that the class of regular languages is closed under bounded prefix-suffix duplication; furthermore, we propose an algorithm which decides whether a regular language is a finite k-prefix-suffix duplication language. An efficient algorithm solving the membership problem for the k-prefix-suffix duplication of a language is also presented. Finally, we define the k-prefix-suffix duplication distance between two words, extend it to languages and show how it can be computed for regular languages.
Internacional
Si
JCR del ISI
Si
Título de la revista
International Journal of Foundations of Computer Science
ISSN
0129-0541
Factor de impacto JCR
0,326
Información de impacto
Datos JCR del año 2013
Volumen
26
DOI
10.1142/S0129054115400079
Número de revista
07
Desde la página
933
Hasta la página
952
Mes
NOVIEMBRE
Ranking
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Marius Dumitran (Faculty of Mathematics and Computer Science, University of Bucharest)
  • Autor: Fco. Javier Gil Rubio (UPM)
  • Autor: Florin Manea (Department of Computer Science, Christian-Albrechts University of Kiel)
  • Autor: Victor Mitrana (UPM)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Grupo de Investigación: Grupo de Computación Natural
S2i 2021 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)