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-kappa(L-1, L-2) of two regular languages L-1 and L-2 and the iterated hairpin lengthening HL kappa*(L) of any language L. Assume that L-1 and L-2 belong to a certain variety of regular languages which satisfies a mild closure property (being closed by a restricted concatenation), then either H-kappa(L-1, L-2) is not regular or it belongs to the same variety as L-1 and L-2. 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   HL kappa*(L). For LDA the situation remains open. (C) 2011 Elsevier B.V. All rights reserved.
hairpin completion regular languages varieties (iterated) hairpin lengthening