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

چکیده انگلیسی
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
Journal: Discrete Applied Mathematics - Volume 171, 10 July 2014, Pages 141–146
نویسندگان
Manolis Christodoulakis, Michalis Christou, Maxime Crochemore, Costas S. Iliopoulos,