Language theoretical properties of hairpin formations (Q418760)

Hairpin completion is an operation on words that models the hairpin formations that occur in biochemical processes and that played an important role in several DNA-computing results. Bounded hairpin completion and hairpin lengthening are two variations of the initial word-operation mentioned above. All these operations have been studied both from language theoretic and algorithmic perspectives. This paper presents a series of results regarding the hairpin completion of two regular languages and the iterated hairpin lengthening of any language. It is worth mentioning that this study and its motivations are, as the authors themselves point out, purely formal; no artificial connection to biology or bio-chemistry is claimed. I consider this paper to be a very nice contribution to the study of hairpin related operations, and I think it brings some fresh ideas and perspectives to the field of bio-inspired language-theory. More precisely, to define such operations one assumes the existence of an antimorphic involution \(\theta\) that defines a pairing relation between the letters of the alphabets; this is supposed to be an abstraction of the Watson-Crick base pairing from biology. By hairpin completion, one can create a hairpin from a word \(\gamma\alpha \beta\theta(\alpha)\) (respectively, \(\theta(\alpha)\beta\alpha\gamma\)) by adding at the end of the word (respectively, at the beginning of the word) the factor \(\theta(\gamma)\), but only when \(\alpha\) is longer than a predefined constant. The hairpin lengthening is defined similarly, with the main difference that in its case we are allowed to add only a prefix (respectively, suffix) of \(\theta(\gamma)\). These operations are extended for languages and their iterated versions are defined. The first important result reported in the paper is that if two regular languages \(L_1\) and \(L_2\) belong to a variety of regular languages which satisfies a certain closure property, defined using a restricted variant of concatenation, then the hairpin completion of \(L_1\) and \(L_2\) is either not regular or it belongs to the same variety. This result can be applied for the class of first-order definable languages in two variables with predicates \(<\) and \(+1\). The proofs of these results connect nicely language theoretic and combinatorial arguments. Secondly, the authors answer an open problem posed by the reviewer et al. from 2010, regarding the closure of the class of regular languages under hairpin lengthening. In fact, the authors show that all classes of the Chomsky hierarchy (as well as other classes of languages) are closed under iterated hairpin lengthening. Again, the proofs are based on combinatorial and language theoretic arguments. The paper concludes with a list of challenging open problems, two of which are the following: Can the regularity of the iterated completion of regular languages be decided? Can the regularity of the one step lengthening of a regular language be decided?