Consistency of multidimensional combinatorial substitutions (Q714822)

Multidimensional combinatorial substitutions are a generalization of morphisms of free monoids, well-known in the formal languages theory. Instead of words, finite contiguous patterns of symbols in \(\mathbb{Z}^{d}\) are considered. A substitution is a rewriting rule describing how to replace a particular symbol of the alphabet by some pattern. Additional concatenation\ rules must be given describing how to assemble the resulting pattern out of the images of two or more neighbor symbols. Such rules may be inconsistent (there can be more than one resulting pattern possible) and the images of symbols may overlap. The paper shows that consistency and non-overlapping are undecidable properties. However, the consistency property is decidable for domino-complete substitutions, where the concatenation rules are given for every possible domino pattern; the non-overlapping property is decidable for consistent domino-complete substitutions.