2019/05/10 by Kari, Jarkko
#37B50 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #Dynamical Systems (math.DS) #F.4.3 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1
paper · doi:10.48550/arxiv.1905.04183
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.