کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430883 688223 2013 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Infinite words containing the minimal number of repetitions
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Infinite words containing the minimal number of repetitions
چکیده انگلیسی

A square in a word is composed of two adjacent occurrences of a nonempty word. This note gives a simple proof and a straight construction of the existence of an infinite binary word that contains only three squares. No infinite binary word can contain fewer squares. The only factors of exponent larger than two that our infinite binary word contains are two cubes. Furthermore, we provide two additional results on alphabets of size 3 and 4. We prove that there exists an infinite overlap-free ternary word containing only one square. On a 4-letter alphabet we show there exists an infinite 3/2+3/2+-free 4-ary word containing only one 3/2-power.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 20, May 2013, Pages 38–42
نویسندگان
,