کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875386 1441947 2018 22 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Partitioned factors in Christoffel and Sturmian words
ترجمه فارسی عنوان
عوامل جدا شده در کلمات کریستفل و استورمی
کلمات کلیدی
تعادل، کلمه کریستف کل، کلمه دایره ای ترکیب بندی، عامل، فرکانس، کلمه مکانیکی، پارتیشن فاکتور تقسیم شده کلمه استرومیا،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Borel and Reutenauer (2006) [3] showed, inter alia, that a word w of length n>1 is conjugate to a Christoffel word if and only if for k=0,1,…,n−1, w has k+1 distinct circular factors of length k. Sturmian words are the infinite counterparts to Christoffel words, characterized as aperiodic but of minimal complexity, i.e., for all n∈N there are n+1 factors of length n. Berthé (1996) [2] showed that the factors of a given length in the Sturmian case have at most three frequencies (probabilities). In this paper we extend to results on factors of both Christoffel words and Sturmian words under fixed partitionings (decompositions of factors of length m into concatenations of words whose lengths are given by a composition of m into k components). Any factor of a Sturmian word (respectively, circular factor of a Christoffel word) thus partitioned into k elements belongs to one of k+1 equivalence classes (varieties). We show how to compute the sizes of the equivalence classes determined by a composition in the case of Christoffel word, and show how to compute the frequencies of the classes in the case of Sturmian words. A version of the finitary case was proved in a very different context (expressed in musical and number-theoretical terms) by Clough and Myerson (1985, 1986) [5], [6]; we use their terminology, variety and multiplicity.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 743, 26 September 2018, Pages 53-63
نویسندگان
, ,