کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
438376 690265 2007 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A note on the number of squares in a word
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A note on the number of squares in a word
چکیده انگلیسی

Fraenkel and Simpson [A.S. Fraenkel, J. Simpson, How many squares can a string contain? J. Combin. Theory Ser. A 82 (1998) 112–120] proved that the number of squares in a word of length n is bounded by 2n. In this note we improve this bound to 2n−Θ(logn). Based on the numerical evidence, the conjectured bound is n.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 380, Issue 3, 28 June 2007, Pages 373-376