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