کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949756 | 1364256 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bannai et al. method proves the d-step conjecture for strings
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Inspired by the d-step approach used for investigating the diameter of polytopes, Deza and Franek introduced the d-step conjecture for runs stating that the number of runs in a string of length n with exactly d distinct symbols is at most nâd. Bannai et al. showed that the number of runs in a string is at most nâ3 for nâ¥5 by mapping each run to a set of starting positions of Lyndon roots. We show that Bannai et al. method proves that the d-step conjecture for runs holds, and stress the structural properties of run-maximal strings. In particular, we show that, up to relabelling, there is a unique run-maximal string of length 2d with d distinct symbols. The number of runs in a string of length n is shown to be at most nâ4 for nâ¥9.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 217, Part 3, 30 January 2017, Pages 488-494
Journal: Discrete Applied Mathematics - Volume 217, Part 3, 30 January 2017, Pages 488-494
نویسندگان
Antoine Deza, Frantisek Franek,