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 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. | |
Internacional
|
Si |
JCR del ISI
|
Si |
Título de la revista
|
International Journal of Foundations of Computer Science |
ISSN
|
0129-0541 |
Factor de impacto JCR
|
0,326 |
Información de impacto
|
Datos JCR del año 2013 |
Volumen
|
26 |
DOI
|
10.1142/S0129054115400079 |
Número de revista
|
07 |
Desde la página
|
933 |
Hasta la página
|
952 |
Mes
|
NOVIEMBRE |
Ranking
|