Low-Complexity Tilings of the Plane




Jarkko Kari

Michal Hospodár, Galina Jirásková, Stavros Konstantinidis

International Conference on Descriptional Complexity of Formal Systems

PublisherSpringer 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

DOIhttps://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.


Last updated on 2024-26-11 at 23:32