کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435729 689931 2010 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On a special class of primitive words
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On a special class of primitive words
چکیده انگلیسی

When representing DNA molecules as words, it is necessary to take into account the fact that a word u encodes basically the same information as its Watson–Crick complement θ(u), where θ denotes the Watson–Crick complementarity function. Thus, an expression which involves only a word u and its complement can be still considered as a repeating sequence. In this context, we define and investigate the properties of a special class of primitive words, called pseudo-primitive words relative to θ or simply θ-primitive words, which cannot be expressed as such repeating sequences. For instance, we prove the existence of a unique θ-primitive root of a given word, and we give some constraints forcing two distinct words to share their θ-primitive root. Also, we present an extension of the well-known Fine and Wilf theorem, for which we give an optimal bound.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 411, Issue 3, 6 January 2010, Pages 617-630