On some algorithmic problems regarding the hairpin completion
We consider a few algorithmic problems regarding the hairpin completion. The first problem we consider is the membership problem  of the hairpin and iterated hairpin completion of a language. We propose an O(nf(n)) O ( n f ( n ) ) and O(n2f(n)) O ( n 2 f ( n ) ) time recognition algorithm for the hairpin completion and iterated hairpin completion, respectively, of a language recognizable in O(f(n)) O ( f ( n ) ) time. We show that the n n factor is not needed in the case of hairpin completion of regular and context-free languages. The n2 n 2 factor is not needed in the case of iterated hairpin completion of context-free languages, but it is reduced to n n in the case of iterated hairpin completion of regular languages. We then define the hairpin completion distance between two words and present a cubic time algorithm for computing this distance. A linear time algorithm for deciding whether or not the hairpin completion distance with respect to a given word is connected is also discussed. Finally, we give a short list of open problems which appear attractive to us.
hairpin completion membership problem iterated hairpin completion hairpin completion distance