×

Palindromes and two-dimensional Sturmian sequences. (English) Zbl 1002.11026

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)].

MSC:

11B85 Automata sequences
68R15 Combinatorics on words
37B10 Symbolic dynamics
PDFBibTeX XMLCite