Observatorio de I+D+i UPM

Memorias de investigación
Communications at congresses:
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
Congress
19th International Conference Implementation and Application of Automata- CIAA 2014
960
Place
Giessen, Alemania
Reviewers
Si
ISBN/ISSN
978-3-319-08845-7
10.1007/978-3-319-08846-4
Start Date
30/07/2014
End Date
02/08/2014
From page
176
To page
187
Lecture Notes in Computer Science Volume: 8587 LNCS
Participants
  • Autor: Marius Dumitran (University of Bucharest)
  • Autor: Fco. Javier Gil Rubio (UPM)
  • Autor: Florin Manea (Christian-Albrechts University of Kiel)
  • 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)