Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
Bounded Prefix-Suffix Duplication
Year:2014
Research Areas
  • Information technology and adata processing
Information
Abstract
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.
International
Si
JCR
Si
Title
Lecture Notes in Computer Science
ISBN
0302-9743
Impact factor JCR
0,402
Impact info
Datos JCR del año 2005
Volume
8587
10.1007/978-3-319-08846-4_13
Journal number
From page
176
To page
187
Month
JULIO
Ranking
Participants
  • Autor: Marius Dumitran (Universidad de Bucarest, Rumania)
  • Autor: Fco. Javier Gil Rubio (UPM)
  • Autor: Florin Manea (Universidad de KIel, Alemania)
  • Autor: Victor Mitrana (UPM)
Research Group, Departaments and Institutes related
  • Creador: Departamento: Sistemas Informáticos
S2i 2020 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)