Consistency of multidimensional combinatorial substitutions

Details Consistency of multidimensional combinatorial substitutions Consistency of multidimensional combinatorial substitutions

2011-12-08

arxiv.org/abs/1112.1841v1

Computer Science

Discrete Mathematics

14 pages

Scientific paper

Multidimensional combinatorial substitutions are rules that replace symbols by finite patterns of symbols in Z^d. We focus on the case where the patterns are not necessarily rectangular, which requires a specific description of the way they are glued together in the image by a substitution. Two problems can arise when defining a substitution in such a way: it can fail to be consistent, and the patterns in an image by the substitution might overlap. We prove that it is undecidable whether a two-dimensional substitution is consistent or overlapping, and we provide practical algorithms to decide these properties in some particular cases.

Affiliated with

Also associated with

No associations

Rating

Consistency of multidimensional combinatorial substitutions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Consistency of multidimensional combinatorial substitutions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Consistency of multidimensional combinatorial substitutions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-548611