Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875386 | Theoretical Computer Science | 2018 | 22 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Norman Carey, David Clampitt,