Low-Complexity Tilings of the Plane

被引：3

作者：

Kari, Jarkko ^{[1
]}

机构：

[1] Univ Turku, Dept Math & Stat, Turku, Finland

来源：

DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2019 | 2019年 / 11612卷

基金：

芬兰科学院;

关键词：

Pattern complexity; Periodicity; Nivat's conjecture; Low complexity configurations; Low complexity subshifts; Commutative algebra; Algebraic subshifts; Domino problem;

D O I：

10.1007/978-3-030-23247-4_2

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A two-dimensional configuration is a coloring of the infinite grid Z(2) with finitely many colors. For a finite subset D of 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 vertical bar D vertical bar, the size of the shape. This extended abstract is a short review of an algebraic method to study periodicity of such low complexity configurations.

引用

页码：35 / 45

页数：11

共 16 条

[1]

[Anonymous], 1912, Bull. Soc. Math. France

[2] On multiple coverings of the infinite rectangular grid with balls of constant radius [J].