TY  - JOUR
A1  - Bordihn, Henning
A1  - Mitrana, Victor
A1  - Paun, Andrei
A1  - Paun, Mihaela
T1  - Hairpin completions and reductions
BT  - semilinearity properties
JF  - Natural computing : an innovative journal bridging biosciences and computer sciences ; an international journal
N2  - This paper is part of the investigation of some operations on words and languages with motivations coming from DNA biochemistry, namely three variants of hairpin completion and three variants of hairpin reduction. Since not all the hairpin completions or reductions of semilinear languages remain semilinear, we study sufficient conditions for semilinear languages to preserve their semilinearity property after applying the non-iterated hairpin completion or hairpin reduction. A similar approach is then applied to the iterated variants of these operations. Along these lines, we define the hairpin reduction root of a language and show that the hairpin reduction root of a semilinear language is not necessarily semilinear except the universal language. A few open problems are finally discussed.
KW  - DNA hairpin formation
KW  - Hairpin completions
KW  - Hairpin reductions
KW  - Semilinearity property
Y1  - 2020
U6  - https://doi.org/10.1007/s11047-020-09797-0
SN  - 1572-9796
VL  - 20
IS  - 2
SP  - 193
EP  - 203
PB  - Springer Science + Business Media B.V.
CY  - Dordrecht
ER  -