Date:

Tue, 12/05/202014:00-15:00

E-Seminar.

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

Join Zoom Meeting

Meeting ID: 922 0743 4115

Password: 681717

Link to recording

https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=88f0050f-9c5d-4622-90af-abb900cbda2b