Jarkko Kari - Low complexity colorings of the two-dimensional grid - Hatfest скачать в хорошем качестве

Jarkko Kari - Low complexity colorings of the two-dimensional grid - Hatfest

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 [1]. 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 [2]. 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 [3]. References [1] J. Kari, M. Szabados. An Algebraic Geometric Approach to Nivat’s Conjecture. Information and Computation 271, pp. 104481 (2020). [2] 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). [3] J. Kari, E. Moutot. Nivat’s conjecture and pattern complexity in algebraic subshifts. Theoretical Computer Science 777, pp. 379–386 (2019). A talk from Hatfest at the Mathematical Institute, University of Oxford. See https://sites.google.com/view/thegrimmnetw... for more information.