Memorias de investigación
Ponencias en congresos:
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
Nombre congreso
19th International Conference Implementation and Application of Automata- CIAA 2014
Tipo de participación
960
Lugar del congreso
Giessen, Alemania
Revisores
Si
ISBN o ISSN
978-3-319-08845-7
DOI
10.1007/978-3-319-08846-4
Fecha inicio congreso
30/07/2014
Fecha fin congreso
02/08/2014
Desde la página
176
Hasta la página
187
Título de las actas
Lecture Notes in Computer Science Volume: 8587 LNCS
Esta actividad pertenece a memorias de investigación
Participantes
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Departamento: Sistemas Informáticos