Observatorio de I+D+i UPM

Memorias de investigación
Research Publications in journals:
Bounded Prefix-Suffix Duplication: Language Theoretic and Algorithmic Results
Year:2015
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 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.
International
Si
JCR
Si
Title
International Journal of Foundations of Computer Science
ISBN
0129-0541
Impact factor JCR
0,326
Impact info
Datos JCR del año 2013
Volume
26
10.1142/S0129054115400079
Journal number
07
From page
933
To page
952
Month
NOVIEMBRE
Ranking
Participants
  • 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)
Research Group, Departaments and Institutes related
  • Creador: Grupo de Investigación: Grupo de Computación Natural
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)