کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436203 689977 2009 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A generalization of Thue freeness for partial words
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A generalization of Thue freeness for partial words
چکیده انگلیسی

This paper approaches the combinatorial problem of Thue freeness for partial words. Partial words are sequences over a finite alphabet that may contain a number of “holes”. First, we give an infinite word over a three-letter alphabet which avoids squares of length greater than two even after we replace an infinite number of positions with holes. Then, we give an infinite word over an eight-letter alphabet that avoids longer squares even after an arbitrary selection of its positions are replaced with holes, and show that the alphabet size is optimal. We find similar results for overlap-free partial words.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issues 8–10, 1 March 2009, Pages 793-800