|
Descripción
|
|
|---|---|
| The hairpin completion is a newly introduced operation on formal languages, inspired by biological phenomena and by DNAcomputing. In this article, we analyse a new variant of the hairpin completion, called hairpin lengthening, which seems more appropriate for a possible bio-lab implementation. The variant considered here concerns the lengthening of the word that forms a hairpin structure, such that this structure is preserved, without necessarily completing the hairpin. First we present a series of language theoretic results regarding the one-step and iterated hairpin lengthening of languages from different classes of the Chomsky hierarchy. Following our biological motivation we also approach several algorithmic properties of this operation. More precisely, we propose an efficient algorithm for the recognition of the iterated hairpin lengthening of a language, and show how it can be particularized to recognize the one-step hairpin lengthening of a language; the cases when the starting language is finite, regular, linear context-free or context-free are discussed. It is worth noting that these results cannot be deduced canonically from the closure properties of the discussed classes of languages.We also propose an algorithm for computing efficiently the hairpin lengthening distance between a word and all its factors; this algorithm can be used to compute the distance between two words, or the common hairpin-lengthening ancestors of two words. | |
|
Internacional
|
Si |
|
JCR del ISI
|
Si |
|
Título de la revista
|
Journal of Logic And Computation |
|
ISSN
|
0955-792X |
|
Factor de impacto JCR
|
0,504 |
|
Información de impacto
|
|
|
Volumen
|
25 |
|
DOI
|
10.1093/logcom/exs076 |
|
Número de revista
|
4 |
|
Desde la página
|
987 |
|
Hasta la página
|
1009 |
|
Mes
|
AGOSTO |
|
Ranking
|
|