(J. Waldmann, 26. Juli 2019)
Goal: investigate reasonable two-dimensional analogues of the concepts of one-dimensional one-sided infinite streams and pattern avoidance.
Status: this is a plan for a student project (September 2019 - September 2020). The student should do some experiments, produce data, and nice visualizations, that may lead to further research.
(all of this is well-known. As a general reference, see Lothaire: (Algebraic) Combinatorics on Words http://www-igm.univ-mlv.fr/~berstel/Lothaire/. On avoiding patterns, cf. Currie: Pattern avoidance: themes and variations https://doi.org/10.1016/j.tcs.2005.01.004 . Also, my lecture notes Kombinatorik Part II https://www.imn.htwk-leipzig.de/~waldmann/edu/ancient/ss00/kombinat/kombinat-pub.ps and https://www.imn.htwk-leipzig.de/~waldmann/etc/stream/)
A stream is a one-sided infinite sequence, sometimes calle omega-word, which is a mapping from N (naturals) to Sigma (finite).
The alphabet of the stream can be mapped to drawing instructions (e.g., 0: turn left and move, 1: turn right and move) that give a two-dimensional visualisation of the stream. We can also use this in the other direction (a geometric property defines a stream), e.g., the representation a mechanical stream approximates a line (with irrational slope).
To handle streams algorithmically (e.g., decide some properties) we need to represent them in some finite way. In general, any program that computes (the mapping of) the stream can be used, but then everything becomes undecidable. Therefore, the class of programs is restricted. One could just consider streams that are eventually periodic (equivalently, constructed by a finite automaton with output, and without input) but for some applications (e.g., pattern avoidance, see below) that would exclude all interesting cases. The following models have been considered:
E.g., the Thue-Morse stream 01101001 …
the Fibonacci stream 01010010 …
A pattern is a finite word containing variables. A pattern is instantiated by substituting variables with non-empty finite words. A stream avoids a pattern if no instance of the pattern occurs as a factor.
E.g., the Thue-Morse stream avoids the pattern “uuu” (but not “uu”, since it appears at position 1, with u substituted by 1). The pattern “uu” cannot be avoided over two letter-alphabets, but it can be avoided over three letters.
There are several generalisations, e.g., the pattern may contain operators
E.g., “x perm(x)” is like “xy” restricted to substitutions where y is a permutation (re-arrangment) of x.
(This is mostly speculation, but it can build on some previous work.)
A 2D-stream (we need a better name!) is a colouring of the first quadrant, i.e., a mapping from N x N to Sigma.
For each variant of representing 1D streams one can try find a 2D generalization.
tilings: contrary to the 1D case (finite automata, eventually periodic), this quickly gets undecidable since we can simulate a Turing machine computation (one axis is space, other axis is time)
(cf. Dora Giammarresi: Tiling Recognizable Two-Dimensional Languages CIAA 2007 https://doi.org/10.1007/978-3-540-75414-5_5)
iterated morphisms: this only seems to work for uniform morphism (all letters are mapped to tiles with identical rectangular shape). But there may be other operations (substitute a unit square with some geometric figure) that work. What does “work” mean? The hard condition is that the full image is (again) a tiling (no overlaps, no uncovered space). We could also allow overlaps, but require that images must agree on the overlapped positions.
(cf. “Reptiles” http://mathworld.wolfram.com/Rep-Tile.html and references given there)
automatic 2D streams: that seems easy: for grid position (x,y), write x and y in binary (or some other base), interleave these words, and let an automaton run on that.
(cf. Chapter 14 of Allouche and Shallit: Automatic Sequences https://cs.uwaterloo.ca/~shallit/asas.html)
catenative definitions: should be possible, but overlaps must be excluded, or be handled, see remark for “iterated morphisms”
geometric properties: by analogy to a 1D stream approximating a sloped line, we could approximate a sloped plane. E.g., for the plane z = f(x,y), with f a linear function, define c(x,y) = if f(x,y) - truncate(f(x,y)) < 0.5 then Blue else Red.
In general, this invites a discussion of how to make a 3D image of a 2D stream. Not a 3D turtle - these exist, but they map 1D to 3D. We need to map a 2D colouring to 3D, that is, assign a “height”, in some interesting way. If we want to compute the height h(x,y) by walking along some path from (0,0) to (x,y), and decrement/increment height step-wise, then this must be independent of the choice of path.
A 2D pattern is a finite figure (a tile) containing variables, that we inted to substitute with rectangles (for the easy case).
The 1D pattern “uu” (sometimes called “sqaure” because we can write it as a polynomial “u^2”) corresponds to (perhaps) the set of patterns “u besides u” and “u atop u”, where we want to avoid both at the same time. This can be done: take the known 1D stream s (over 3 letters) that avoids uu. Define a 2D coloring with 9 colours by c(x,y) = (s(x),s(y)). Can we do this with fewer colours?
Note that for 2D stream, to avoid “u besides u” (“u atop u”) it is enough to avoid instances where u is a rectangle of height one (width one)
[added July 26] This fits a remark in Currie: “Pattern Avoidance” where a colouring of the quadrant should avoid 1D patterns along certain lines (horizonal, vertical, diagonal). But we may want to consider other patterns, e.g., “xy” atop “yx”. Then, both x and y should be substituted with rectangles of identical shape (not necessarily squares).
As in the 1D case, a question “is pattern P avoidable” can be handled in several ways:
If we have a model instance that looks good, then we need a proof that the property (pattern avoidance) does hold. This can be done on paper, or we can even automate that. This could be hard. I don’t know whether avoiding pattern is decidable for HD0L words. It is, for automatic words: Henshall and Shallit: Automatic Theorem-Proving in Combinatorics on Words https://arxiv.org/abs/1203.3758