Пятница, 2 сентября, ауд. 106. Начало в 17:00.
Докладчик: Jarkko Kari (University of Turku).
Тема: On the periodicity of multidimensional words of low complexity.
Abstract
Let w : Z^d -> A be an infinite d-dimensional word over a finite alphabet A, and let D be a finite subset of Z^d, the d-dimensional integer grid. The D-patterns of w are the patterns of shape D that appear in w, that is, patterns t(w)|D where t spans over all translations. We say that w has low D-complexity if there are at most |D| distinct D-patterns in w. We study regularities enforced on w by such low complexity assumption. In particular, we are interested on periodicity, that is, whether there exists a non-trivial translation t such that t(w)=w. We use algebraic geometry to show that if w has low D-complexity for any D then w decomposes into a finite number of periodic components. We apply such decomposition to study Nivat's conjecture: the claim that if a two-dimensional w has low D-complexity for a rectangle D then w is periodic. We prove an asymptotic version that states that any two-dimensional non-periodic w can have low D-complexity only for finitely many distinct rectangles D.
