ON THE DETERMINISM OF PATHS ON SUBSTITUTION COMPLEXES

The work is devoted to the study of the combinatorial properties of determinism for a family of substitution complexes consisting of quadrangles glued together side-to-side. These properties are useful in constructing algebraic structures with a finite number of defining relations. In particular, this method was used to construct a finitely defined infinite nilsemigroup satisfying the identity x9 = 0. This construction solves the problem of L.N. Shevrin and M.V. Sapir. In this paper, we study the possibility of coloring the entire family of complexes in a finite number of colors, for which the weak determinism property is satisfied: if the colors of the three vertices of a certain quadrilateral are known, then the color of the fourth side is uniquely determined, except in some cases of a special arrangement of the quadrilateral. Even weak determinism is enough to construct a finitely defined nilsemigroup; when using this construction, the proof is reduced in scope. The properties of determinism were studied earlier within the framework of the theory of tessellations; in particular, Kari and Papasoglu constructed a set of square tiles that allowed only aperiodic tessellations of the plane and had determinism: the colors of the two adjacent edges were uniquely determined by the colors of the two remaining edges.

determinicity, aperiodic tilings, finitely presented semigroups, burnside-type problems