کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650515 1342490 2008 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Unbordered factors and Lyndon words
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Unbordered factors and Lyndon words
چکیده انگلیسی

A primitive word ww is a Lyndon word if ww is minimal among all its conjugates with respect to some lexicographic order. A word ww is bordered if there is a nonempty word u   such that w=uvuw=uvu for some word vv. A right extension of a word ww of length n is a word wu where all factors longer than n are bordered. A right extension wu   of ww is called trivial if there exists a positive integer k   such that wk=uvwk=uv for some word vv.We prove that Lyndon words have only trivial right extensions. Moreover, we give a conjecture which characterizes a property of every word ww which has a nontrivial right extension of length 2|w|-22|w|-2.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 11, 6 June 2008, Pages 2261–2264
نویسندگان
, , ,