کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418495 681674 2012 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Counter-intuitive answers to some questions concerning minimal-palindromic extensions of binary words
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Counter-intuitive answers to some questions concerning minimal-palindromic extensions of binary words
چکیده انگلیسی

In [Š. Holub, K. Saari, On highly palindromic words, Discrete Appl. Math. 157 (2009) 953–959] the authors proposed to measure the degree of “palindromicity” of a binary word ww by ratio |rws||w|, where the word rwsrws is minimal-palindromic–that is, does not contain palindromic subwords of length greater than ⌈|w|2⌉–and the length |r|+|s||r|+|s| is as small as possible. It was asked whether the words of a given length nn which reach the maximal possible ratio |rws||w| among the words of length nn are always palindromes. It was further asked whether it can be assumed, w.l.o.g., that rr and ss are of form 0∗0∗ or 1∗1∗, or at least 0∗1∗0∗1∗ or 1∗0∗1∗0∗. We negatively answer these questions, and also one further question of a similar kind.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issues 1–2, January 2012, Pages 181–186
نویسندگان
,