Effective closed subshifts in 1D can be implemented in 2D

2010/03/16 by Durand, Bruno, Romashchenko, Andrei, Shen, Alexander · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1003.3103

Abstract

In this paper we use fixed point tilings to answer a question posed by Michael Hochman and show that every one-dimensional effectively closed subshift can be implemented by a local rule in two dimensions. The proof uses the fixed-point construction of an aperiodic tile set and its extensions.

Cited by

• Parametrized complexity of relations between multidimensional subshifts

Related

• 1D Effectively Closed Subshifts and 2D Tilings
• Local generation of tilings
• Fixed-point tile sets and their applications
• Hierarchy and Expansiveness in Two-Dimensional Subshifts of Finite Type
• Aperiodic tilings with one prototile and low complexity atlas matching rules