کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437217 690090 2012 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Square-free words obtained from prefixes by permutations
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Square-free words obtained from prefixes by permutations
چکیده انگلیسی

An infinite square-free word w over a three letter alphabet T is said to have a k-stem σ if w=σw1w2⋯ where for each i, there exists a permutation πi of T which extended to a morphism gives wi=πi(σ). We show that there exists an infinite k-stem word for k=1,2,3,9 and 13≤k≤19, but not for 4≤k≤8 and 10≤k≤12. The problem whether k-stem words exist for each k≥20 remains open.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 429, 20 April 2012, Pages 128-133