کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
434633 689770 2013 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Reversible Christoffel factorizations
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Reversible Christoffel factorizations
چکیده انگلیسی

We define a family of natural decompositions of Sturmian words in Christoffel words, called reversible Christoffel (RC) factorizations. They arise from the observation that two Sturmian words with the same language have (almost always) arbitrarily long Abelian equivalent prefixes. Using the three gap theorem, we prove that in each RC factorization, only 2 or 3 distinct Christoffel words may occur. We begin the study of such factorizations, considered as infinite words over 2 or 3 letters, and show that in the general case they are either Sturmian words, or obtained by a three-interval exchange transformation.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 495, 15 July 2013, Pages 17-24