Observatorio de I+D+i UPM

Memorias de investigación
Artículos en revistas:
Bounded Prefix-Suffix Duplication
Año:2014
Á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 prefix or suffix, whose length is bounded by a constant, of a given word. We give a sufficient condition for the closure under bounded prefix-suffix duplication of a class of languages. Consequently, the class of regular languages is closed under bounded prefix-suffix duplication; furthermore, we propose an algorithm deciding 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
Lecture Notes in Computer Science
ISSN
0302-9743
Factor de impacto JCR
0,402
Información de impacto
Datos JCR del año 2005
Volumen
8587
DOI
10.1007/978-3-319-08846-4_13
Número de revista
Desde la página
176
Hasta la página
187
Mes
JULIO
Ranking
Esta actividad pertenece a memorias de investigación
Participantes
  • Autor: Marius Dumitran (Universidad de Bucarest, Rumania)
  • Autor: Fco. Javier Gil Rubio (UPM)
  • Autor: Florin Manea (Universidad de KIel, Alemania)
  • Autor: Victor Mitrana (UPM)
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Departamento: Sistemas Informáticos
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)