Berthé, Valérie; Vuillon, Laurent Palindromes and two-dimensional Sturmian sequences. (English) Zbl 1002.11026 J. Autom. Lang. Comb. 6, No. 2, 121-138 (2001). Sturmian sequences can be defined as sequences \((u_n)_{n\geq 0}\) for which there exist an irrational number \(\alpha\) and a real number \(\beta\in (0,1)\) such that \[ \begin{alignedat}{3} &\text{either}&\quad &\forall n\geq 0 &\quad u_n&= \bigl\lfloor (n+1)\alpha+\beta \bigr\rfloor- \bigl\lfloor n\alpha+\beta \bigr\rfloor\\ &\text{or}&\quad &\forall n\geq 0 &\quad u_n&= \bigl\lceil (n+1)\alpha+\beta \bigr\rceil- \bigl\lceil n\alpha+\beta \bigr\rceil. \end{alignedat} \] These sequences were introduced by M. Morse and G. A. Hedlund in 1940 [Am. J. Math. 62, 1-42 (1940; Zbl 0022.34003)] and can be defined in many equivalent ways. One of these consists in counting the palindromic blocks that occur in these sequences: a sequence is Sturmian if and only if it has exactly two blocks each of odd length and exactly one block of even length [this is a result of X. Droubay and G. Pirillo, Theor. Comput. Sci. 223, 73-85 (1999; Zbl 0930.68116); a particular case was given by X. Droubay, Inf. Process. Lett. 55, 217-221 (1995; Zbl 1004.68537)]. What should be the definition of a two-dimensional Sturmian sequence? The equivalent conditions mentioned above have natural 2D generalizations, but these generalizations are no longer equivalent. In the paper under review the authors study a 2D generalization of Sturmian sequences by means of a binary coding of a \(\mathbb{Z}^2\)-action on \(\mathbb{R}/\mathbb{Z}\) defined by two irrational rotations. They prove that a 2D uniformly recurrent sequence on \(\{0,1\}\) is Sturmian in this sense if and only if it contains exactly one centro-symmetric rectangular block of size \((m,n)\) if \(m\) is even and \(n\) odd, and exactly two such blocks otherwise. The last part of the paper gives applications to plane partitions. Note that Reference [14] has appeared [Theor. Comput. Sci. 255, 539-553 (2001; Zbl 0981.68126)]. Reviewer: Jean-Paul Allouche (Orsay) Cited in 18 Documents MSC: 11B85 Automata sequences 68R15 Combinatorics on words 37B10 Symbolic dynamics Keywords:palindromes; discrete planes; binary coding; irrational rotations; 2D uniformly recurrent sequence; plane partitions Citations:Zbl 0022.34003; Zbl 0930.68116; Zbl 1004.68537; Zbl 0981.68126 PDFBibTeX XMLCite \textit{V. Berthé} and \textit{L. Vuillon}, J. Autom. Lang. Comb. 6, No. 2, 121--138 (2001; Zbl 1002.11026)