Balanced word: Difference between revisions

Line 6:

== Properties ==

* A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</math>. In particular, binary balanced periodic words are MOS words.

* A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</math>.<ref>Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.</ref> In particular, binary balanced periodic words are MOS words.

* If ''w'' is an aperiodic infinite balanced word, then ''w'' is constructed via a finite sequence of "congruence substitutions" beginning with a Sturmian word. Over 3 or more letters, all such words have a density vector (vector of relative letter frequencies) '''a''' = (a_i) which has a pair of components that are equal. <ref>Brauner, N., Crama, Y., Delaporte, E., Jost, V., & Libralesso, L. (2019). Do balanced words have a short period?. Theoretical Computer Science, 793, 169-180.</ref>

* Some periodic balanced words are not obtainable via congruence substitutions. For alphabets of size ''N'' = 3, ..., 7, the only examples of density vectors with all components distinct are permutations of (1, 2, 4, ..., 2<sup>''N''-1</sup>) arising from the Fraenkel word ''F''<sub>''N''</sub>, defined via <math>F_1 = \mathbf{0}, F_n = F_{n-1} \mathbf{(n-1)} F_{n-1}.</math> The assertion that this is true for all ''N'' ≥ 3 is Fraenkel's conjecture.

@@ Line 6: / Line 6: @@
 == Properties ==
-* A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</math>. In particular, binary balanced periodic words are MOS words.
+* A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</math>.<ref>Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.</ref> In particular, binary balanced periodic words are MOS words.
 * If ''w'' is an aperiodic infinite balanced word, then ''w'' is constructed via a finite sequence of "congruence substitutions" beginning with a Sturmian word. Over 3 or more letters, all such words have a density vector (vector of relative letter frequencies) '''a''' = (a_i) which has a pair of components that are equal. <ref>Brauner, N., Crama, Y., Delaporte, E., Jost, V., & Libralesso, L. (2019). Do balanced words have a short period?. Theoretical Computer Science, 793, 169-180.</ref>
 * Some periodic balanced words are not obtainable via congruence substitutions. For alphabets of size ''N'' = 3, ..., 7, the only examples of density vectors with all components distinct are permutations of (1, 2, 4, ..., 2<sup>''N''-1</sup>) arising from the Fraenkel word ''F''<sub>''N''</sub>, defined via <math>F_1 = \mathbf{0}, F_n = F_{n-1} \mathbf{(n-1)} F_{n-1}.</math> The assertion that this is true for all ''N'' &ge; 3 is Fraenkel's conjecture.