Proceedings of the American Mathematical Society · 2012 · 10 citations · 10 references
Natural SciencesMathematicsComputational GeometryRepresentation TheoryTopologyLinear TransformationsOrdering TransformationsMultidimensional ShiftsShift SpacesSofic Shifts
In one dimension, sofic shifts are fairly well understood and are special examples of shift spaces which must satisfy very restrictive properties. However, in multiple dimensions there are very few known conditions which guarantee nonsoficity of a shift space. In this paper, we show that for any Z d sofic shift X which satisfies a uniform mixing condition called block gluing in all directions e 2 , . . . , e d , the set of legal rows of X in the e 1 -direction has a synchronizing word. This allows us to define a (new) large class of nonsofic Z d shift spaces.
10
The undecidability of the domino problem
Robert E. Berger · Memoirs of the American Mathematical Society · 1966 · 974 citations
Proving Theorems by Pattern Recognition - II
Hao Wang · Bell System Technical Journal · 1961 · 871 citations