%0 Conference Proceedings
%T Low-Complexity Tilings of the Plane
%+ Department of Mathematics and Statistics [uni. Turku]
%A Kari, Jarkko
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 21th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Košice, Slovakia
%Y Michal Hospodár
%Y Galina Jirásková
%Y Stavros Konstantinidis
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-11612
%P 35-45
%8 2019-07-17
%D 2019
%R 10.1007/978-3-030-23247-4_2
%K Pattern complexity
%K Periodicity
%K Nivat’s conjecture
%K Low complexity configurations
%K Low complexity subshifts
%K Commutative algebra
%K Algebraic subshifts
%K Domino problem
%Z Computer Science [cs]Conference papers
%X A two-dimensional configuration is a coloring of the infinite grid $$\mathbb {Z}^2$$ with finitely many colors. For a finite subset D of $$\mathbb {Z}^2$$, the D-patterns of a configuration are the colored 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. A configuration is considered having low complexity with respect to shape D if the number of distinct D-patterns is at most |D|, the size of the shape. This extended abstract is a short review of an algebraic method to study periodicity of such low complexity configurations.
%G English
%Z TC 1
%Z WG 1.02
%2 https://inria.hal.science/hal-02387291/document
%2 https://inria.hal.science/hal-02387291/file/480958_1_En_2_Chapter.pdf
%L hal-02387291
%U https://inria.hal.science/hal-02387291
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-11612