Balanced word: Difference between revisions
Jump to navigation
Jump to search
Tags: Mobile edit Mobile web edit |
Tags: Mobile edit Mobile web edit |
||
| Line 7: | Line 7: | ||
* 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. 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> | * 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>) from the Fraenkel word ''F''<sub>''N''</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 ''N'' = 3, ..., 7, the only examples of density vectors with all components distinct are permutations of (1, 2, 4, ..., 2<sup>''N''-1</sup>) from the Fraenkel word ''F''<sub>''N''</sub>, defined via <math>F_0 = \mathbf{0}, F_n = F_{n-1} \mathbf{(n-1)} F_{n-1}.</math> | ||
<!-- | <!-- | ||
** A ''congruence word'' is a word u where the set of occurrences of each letter m in u is of the form <math>\{a_m n + b_m : n \in \mathbb{N}\},</math> for integers a_m and b_m. | ** A ''congruence word'' is a word u where the set of occurrences of each letter m in u is of the form <math>\{a_m n + b_m : n \in \mathbb{N}\},</math> for integers a_m and b_m. | ||
Revision as of 15:25, 31 December 2023
Let d ≥ 0. A word or necklace s is balanced if its balance satisfies the following:
[math]\displaystyle{ \operatorname{balance}(s) := \max \big\{ \big| |w|_{x_i} - |w'|_{x_i} \big| : x_i \text{ is a letter of }s\text{ and }k = \operatorname{len}(w) = \operatorname{len}(w') \big\} \leq 1, }[/math]
where |u|xi is the number of occurrences of the letter xi in the word u.
Properties
- A balanced word or necklace on N letters has a maximum variety bound of [math]\displaystyle{ 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. 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. [1]
- 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, ..., 2N-1) from the Fraenkel word FN, defined via [math]\displaystyle{ F_0 = \mathbf{0}, F_n = F_{n-1} \mathbf{(n-1)} F_{n-1}. }[/math]
Generalizations
References
- ↑ Brauner, N., Crama, Y., Delaporte, E., Jost, V., & Libralesso, L. (2019). Do balanced words have a short period?. Theoretical Computer Science, 793, 169-180.