کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
434045 689673 2015 28 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Studies on finite Sturmian words
ترجمه فارسی عنوان
مطالعات بر روی کلمات محدود استورمی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Several properties of finite Sturmian words are proved. The inverse of the Richomme–Séébold bijection between factor sets of given length of Sturmian sequences and left special Sturmian words is constructed (using circular factors of Christoffel words) and studied. The Labbé bijection between Christoffel words and left special Sturmian words is introduced and studied. Factor sets are classified by two types: the two classes are characterized by conjugation and periodicity properties. The two classes are related to the Rauzy graph. A normal form for finite Sturmian words is given, following a result of de Luca and De Luca. Several classes of Sturmian words are characterized through this normal form: left or right special words, bispecial words, palindromes, central words. The normal form is used to derive a proof of the Lipatov–Mignosi formula for the number of Sturmian words of given length; to produce a linear algorithm which checks if a word is Sturmian and which computes its normal form; to construct algorithmically the contraction and completion in various classes of Sturmian words; to compute the de Luca palindromic closure of any Sturmian word and prove that it is Sturmian. The completion is related to the de Luca palindromization function and it is shown that the sets of directive words of central words of even and odd length are rational group languages. Christoffel words are characterized in several ways: an extension of a result of Chuan; an extension of a result of Droubay–Pirillo, by counting circular factors; by counting Lyndon factors. A special Christoffel word is constructed having length a given Markoff number. A bivariate count of special Sturmian words is given, using ideas of Bédaride, Domenjoud, Jamet and Rémy. Open problems are given.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 591, 2 August 2015, Pages 106–133
نویسندگان
,