Computer Science – Formal Languages and Automata Theory
Scientific paper
2011-02-17
Fundamenta Informaticae 110 (2011) 255--269
Computer Science
Formal Languages and Automata Theory
17 pages, 2 figures
Scientific paper
10.3233/FI-2011-542
Hairpin completion and its variant called bounded hairpin completion are operations on formal languages, inspired by a hairpin formation in molecular biology. Another variant called hairpin lengthening has been recently introduced and studied on the closure properties and algorithmic problems concerning several families of languages. In this paper, we introduce a new operation of this kind, called hairpin incompletion which is not only an extension of bounded hairpin completion, but also a restricted (bounded) variant of hairpin lengthening. Further, the hairpin incompletion operation provides a formal language theoretic framework that models a bio-molecular technique nowadays known as Whiplash PCR. We study the closure properties of language families under both the operation and its iterated version. We show that a family of languages closed under intersection with regular sets, concatenation with regular sets, and finite union is closed under one-sided iterated hairpin incompletion, and that a family of languages containing all linear languages and closed under circular permutation, left derivative and substitution is also closed under iterated hairpin incompletion.
Okubo Fumiya
Yokomori Takashi
No associations
LandOfFree
On the Hairpin Incompletion does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Hairpin Incompletion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Hairpin Incompletion will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-380151