کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420539 683952 2009 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On some algorithmic problems regarding the hairpin completion
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
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(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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 9, 6 May 2009, Pages 2143–2152
نویسندگان
, , ,