کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420671 683968 2009 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On highly palindromic words
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On highly palindromic words
چکیده انگلیسی

We study some properties of palindromic (scattered) subwords of binary words. In view of the classical problem on subwords, we show that the set of palindromic subwords of a word characterizes the word up to reversal.Since each word trivially contains a palindromic subword of length at least half of its length–a power of the prevalent letter–we call a word that does not contain any palindromic subword longer than half of its length minimal palindromic. We show that every minimal palindromic word is abelian unbordered, that is, no proper suffix of the word can be obtained by permuting the letters of a proper prefix.We also propose to measure the degree of palindromicity of a word ww by the ratio |rws|/|w||rws|/|w|, where the word rwsrws is minimal palindromic and rsrs is as short as possible. We prove that the ratio is always bounded by four, and construct a sequence of words that achieves this bound asymptotically.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 5, 6 March 2009, Pages 953–959
نویسندگان
, ,