|
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
|
|