Balanced words. (English) Zbl 1070.68129

Vuillon, Laurent

Bull. Belg. Math. Soc. - Simon Stevin, Suppl., 787-805 (2003).

A finite or infinite word defined over a finite alphabet \({\mathcal A}\) is said to be balanced if, for any pair of factors \((W,W')\) with the same length and any element \(a\) in \({\mathcal A}\), we have \[ \left| | W|_a-| W'|_a\right|\leq 1. \] Here \(| W|_a\) denotes the number of occurrences of the letter \(a\) in the word \(W\).
The paper under review presents an interesting survey of the notion of balance. Classical results are recalled, but the purpose of the author is mainly to focus on various generalizations of this notion with applications and with open problems in number theory, theoretical computer science or ergodic theory. Most of the mentioned results correspond to recent works.

Reviewer: Boris Adamczewski (Lyon)

MSC:

68R15	Combinatorics on words
05A05	Permutations, words, matrices
37B10	Symbolic dynamics

Keywords:

combinatorics on words; balance property; Sturmian words