Balanced word: Difference between revisions

Line 5:

where |''u''|''x''''i'' is the number of occurrences of the letter ''x''''i'' in the word ''u''.

== 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" from infinite balanced words on 2 letters.<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" from infinite balanced words on 2 letters.<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><!--

** 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 substitution'' involves replacing the ''k''th occurrence of a fixed letter ''j'' in ''w'' with the ''k''th letter of ''u'' where ''u'' is a congruence word over a set of letters disjoint from that of ''w'' for all positive integers ''k''.-->

@@ Line 5: / Line 5: @@
 where |''u''|<sub>''x''<sub>''i''</sub></sub> is the number of occurrences of the letter ''x''<sub>''i''</sub> in the word ''u''.
 == 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" from infinite balanced words on 2 letters.<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" from infinite balanced words on 2 letters.<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><!--
 ** 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 substitution'' involves replacing the ''k''th occurrence of a fixed letter ''j'' in ''w'' with the ''k''th letter of ''u'' where ''u'' is a congruence word over a set of letters disjoint from that of ''w'' for all positive integers ''k''.-->