Language theoretical properties of hairpin formations

Hairpin formations arise in biochemical processes and play an important role in DNA-computing. We study language theoretical properties of hairpin formations and our new results concern the hairpin completion Hκ(L1,L2) of two regular languages L1 and L2 and the iterated hairpin lengthening of any language L.Assume that L1 and L2 belong to a certain variety of regular languages which satisfies a mild closure property (being closed by a restricted concatenation), then either Hκ(L1,L2) is not regular or it belongs to the same variety as L1 and L2. This result applies, in particular, to the class of first-order definable languages (which is the class of aperiodic or star-free languages) and it applies to the class of first-order definable languages in two variables with predicates < and successor +1 (i. e., languages in the variety ).Furthermore, we solve an open question from Manea et al. [15], : we prove that regular languages are closed under iterated hairpin lengthening. (This has been independently shown in Manea et al. [16].) However, the result here is more precise: if L belongs to a class of languages which satisfies a certain closure property with respect to locally testable languages, then belongs to the same class. This applies to the class of aperiodic languages and many other classes. We also show that the variety is not closed under the operation . For the situation remains open.