کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419337 683783 2014 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Abelian borders in binary words
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Abelian borders in binary words
چکیده انگلیسی

In this article we study the appearance of abelian borders in binary words, a notion closely related to the abelian period of a word. We show how many binary words have shortest border of a given length by identifying relations with Dyck words. Furthermore, we give some bounds on the number of abelian border-free words of a given length and on the number of abelian words of a given length that have at least one abelian border. Finally, using some techniques employed in a recent paper by Christodoulakis et al. (2013), we show that there exists an algorithm that finds the shortest abelian border of a binary word that is not abelian border-free in Θ(n) time on average.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 171, 10 July 2014, Pages 141–146
نویسندگان
, , , ,