Low-Complexity Tilings of the Plane
: Jarkko Kari
: Michal Hospodár, Galina Jirásková, Stavros Konstantinidis
: International Conference on Descriptional Complexity of Formal Systems
Publisher: Springer Verlag
: 2019
Lecture Notes in Computer Science
: Descriptional Complexity of Formal Systems: 21st IFIP WG 1.02 International Conference, DCFS 2019 Košice, Slovakia, July 17–19, 2019
: 11612
: 35
: 45
: 978-3-030-23246-7
: 978-3-030-23247-4
: 0302-9743
DOI: https://doi.org/10.1007/978-3-030-23247-4_2
: https://research.utu.fi/converis/portal/detail/Publication/41851167
A two-dimensional configuration is a coloring of the infinite grid Z2 with finitely many colors. For a finite subset D of Z2, 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.
Algebraic subshifts, Commutative algebra, domino problem, Low complexity configurations, Low complexity subshifts, Nivat’s conjecture, Pattern complexity, periodicity
