Balanced word: Difference between revisions
No edit summary Tags: Mobile edit Mobile web edit |
Tags: Mobile edit Mobile web edit |
||
| Line 6: | Line 6: | ||
== Properties == | == Properties == | ||
* A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</math>. | * A balanced word or necklace on ''N'' letters has a [[maximum variety]] bound of <math> N \choose {\lceil N/2 \rceil}</math>. | ||
* If ''w'' is an aperiodic infinite balanced word, then ''w'' is constructed via a finite sequence of "congruence substitutions" beginning with a Sturmian word. | * 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 ''d'' = 3, ..., 7, the only examples of density vectors with all components distinct are permutations of (1, 2, 4, ..., 2<sup>''d''-1</sup>) from the Fraenkel word ''F''<sub>''d''</sub>, defined via <math>F_0 = \mathbf{0}, F_n = F_{n-1} \mathbf{n} F_{n-1}.</math> | * Some periodic balanced words are not obtainable via congruence substitutions. For alphabets of size ''d'' = 3, ..., 7, the only examples of density vectors with all components distinct are permutations of (1, 2, 4, ..., 2<sup>''d''-1</sup>) from the Fraenkel word ''F''<sub>''d''</sub>, defined via <math>F_0 = \mathbf{0}, F_n = F_{n-1} \mathbf{n} F_{n-1}.</math> | ||
<!-- | <!-- | ||