کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435709 689929 2015 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On some generalizations of abelian power avoidability
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On some generalizations of abelian power avoidability
چکیده انگلیسی

We prove that 2-abelian-cubes are avoidable over a binary alphabet and that 3-abelian-squares are avoidable over a ternary alphabet, answering positively to two questions of Karhumäki et al. We also show the existence of infinite additive-cube-free words on several ternary alphabets. To achieve this, we give sufficient conditions for a morphism to be k-abelian-n-power-free (resp. additive-n-power-free), and then we give several morphisms which respect these conditions.Additionally, all our constructions show that the number of such words grows exponen-tially. As a corollary, we get a new lower bound of 31/19=1.059526…31/19=1.059526… for the growth rate of abelian-cube-free words.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 601, 11 October 2015, Pages 39–46
نویسندگان
,