Abstract: A two-dimensional configuration is a coloring of the infinite grid Z^2 using a finite number of colors. For a finite subset D of Z^2, the D-patterns of a configuration are the patterns of shape D that appear in the configuration. The number of distinct D-patterns of a configuration is a natural measure of its complexity. We consider low-complexity configurations where the number of distinct D-patterns is at most |D|, the size of the shape. We use algebraic tools to study periodicity of such configurations . In the case D is a rectangle - or in fact any convex shape - we establish that a uniformly recurrent configuration that has low-complexity with respect to shape D must be periodic . This implies an algorithm to determine if a given collection of mn rectangular patterns of size mxn admit a configuration containing only these patterns. (Without the complexity bound the question is the well-known undecidable domino problem.) We also show, for an arbitrary shape D, that a low-complexity configuration must be periodic if it comes from the well-known Ledrappier subshift, or from a wide family of other similar algebraic subshifts .
 J. Kari, M. Szabados. An Algebraic Geometric Approach to Nivat’s Conjecture. Information and Computation 271, pp. 104481 (2020).
 J. Kari, E. Moutot. Decidability and Periodicity of Low Complexity Tilings, proceedings of STACS 2020, the 37th International Symposium on Theoretical Aspects of Computer Science, LIPIcs 154, pp.14:1-14:12 (2020).
 J. Kari, E. Moutot. Nivat’s conjecture and pattern complexity in algebraic subshifts. Theoretical Computer Science 777, pp. 379–386 (2019).
Join Zoom Meeting
Meeting ID: 922 0743 4115
Link to recording
Tue, 12/05/2020 - 14:00 to 15:00