کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420539 | 683952 | 2009 | 10 صفحه PDF | دانلود رایگان |

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(nf(n)) and O(n2f(n))O(n2f(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 nn factor is not needed in the case of hairpin completion of regular and context-free languages. The n2n2 factor is not needed in the case of iterated hairpin completion of context-free languages, but it is reduced to nn 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.
Journal: Discrete Applied Mathematics - Volume 157, Issue 9, 6 May 2009, Pages 2143–2152