Non-uniform cellular automata (NUCA) are an extension of cellular automata with multiple local rules in different cells. We show that if the distribution of local rules is uniformly recurrent, or recurrent in the one-dimensional case, the Garden of Eden theorem holds. We also show that for any one-dimensional non-recurrent distribution, there is a substitution of local rules that defines a NUCA which does not satisfy the Garden of Eden theorem. Finally, we show that a one-dimensional rule distribution asymptotic to recurrent distribution defines a surjunctive NUCA.

A d-dimensional configuration is a coloring of the infinite grid ℤ^d using a finite number of colors. For a finite subset D ⊆ ℤ^d, the D-patterns of a configuration are the patterns of shape D that appear in the configuration. A configuration is said to be admitted by these patterns. The number of distinct D-patterns in a configuration is a natural measure of its complexity. We focus on low complexity configurations, where the number of distinct D-patterns is at most |D|, the size of the shape. This framework includes the notorious open Nivat’s conjecture and the recently solved Periodic Tiling problem. We use algebraic tools to study the periodicity of low complexity configurations. In the two-dimensional case, if D ⊆ ℤ² is a rectangle or any convex shape, we establish an algorithm to determine if a given collection of |D| patterns admits any configuration. This is based on the fact that if the given patterns admit a configuration, then they admit a periodic configuration. We also demonstrate that a two-dimensional low complexity configuration must be periodic if it originates from the well-known Ledrappier subshift or from several other algebraically defined subshifts.

Abstract We study forced periodicity of two-dimensional configurations under certain constraints and use an algebraic approach to multidimensional symbolic dynamics in which d-dimensional configurations and finite patterns are presented as formal power series and Laurent polynomials, respectively, in d variables. We consider perfect colorings that are configurations such that the number of points of a given color in the neighborhood of any point depends only on the color of the point for some fixed relative neighborhood, and we show that by choosing the alphabet suitably any perfect coloring has a non-trivial annihilator, that is, there exists a Laurent polynomial whose formal product with the power series presenting the perfect coloring is zero. Using known results we obtain a sufficient condition for forced periodicity of two-dimensional perfect colorings. As corollaries of this result we get simple new proofs for known results of forced periodicity on the square and the triangular grids. Moreover, we obtain a new result concerning forced periodicity of perfect colorings in the king grid. We also consider perfect colorings of a particularly simple type: configurations that have low abelian complexity with respect to some shape, and we generalize a result that gives a sufficient condition for such configurations to be necessarily periodic. Also, some algorithmic aspects are considered.

Abstract A d-dimensional configuration $$c:\mathbb {Z}^d\longrightarrow A$$ c : Z d ⟶ A is a coloring of the d-dimensional infinite grid by elements of a finite alphabet $$A\subseteq \mathbb {Z}$$ A ⊆ Z . The configuration c has an annihilator if a non-trivial linear combination of finitely many translations of c is the zero configuration. Writing c as a d-variate formal power series, the annihilator is conveniently expressed as a d-variate Laurent polynomial f whose formal product with c is the zero power series. More generally, if the formal product is a strongly periodic configuration, we call the polynomial f a periodizer of c. A common annihilator (periodizer) of a set of configurations is called an annihilator (periodizer, respectively) of the set. In particular, we consider annihilators and periodizers of d-dimensional subshifts, that is, sets of configurations defined by disallowing some local patterns. We show that a $$(d-1)$$ ( d - 1 ) -dimensional linear subspace $$S\subseteq \mathbb {R}^d$$ S ⊆ R d is expansive for a subshift if the subshift has a periodizer whose support contains exactly one element of S. As a subshift is known to be finite if all $$(d-1)$$ ( d - 1 ) -dimensional subspaces are expansive, we obtain a simple necessary condition on the periodizers that guarantees finiteness of a subshift or, equivalently, strong periodicity of a configuration. We provide examples in terms of tilings of $$\mathbb {Z}^d$$ Z d by translations of a single tile.

Abstract In this paper we study colorings (or tilings) of the two-dimensional grid ${\mathbb {Z}}^{2}$ ℤ2 . A coloring is said to be valid with respect to a setPofn×mrectangular patterns if alln×msub-patterns of the coloring are inP. A coloringcis said to be of low complexity with respect to a rectangle if there exist $m,n\in \mathbb {N}$ m,n∈ℕ and a setPofn×mrectangular patterns such thatcis valid with respect toPand |P|≤nm. Open since it was stated in 1997, Nivat’s conjecture states that such a coloring is necessarily periodic. If Nivat’s conjecture is true, all valid colorings with respect toPsuch that |P|≤mnmust be periodic. We prove that there exists at least one periodic coloring among the valid ones. We use this result to investigate the tiling problem, also known as the domino problem, which is well known to be undecidable in its full generality. However, we show that it is decidable in the low-complexity setting. Then, we use our result to show that Nivat’s conjecture holds for uniformly recurrent configurations. These results also extend to other convex shapes in place of the rectangle. After that, we prove that thenmbound is multiplicatively optimal for the decidability of the domino problem, as for allε> 0 it is undecidable to determine if there exists a valid coloring for a given $m,n\in \mathbb {N}$ m,n∈ℕ and set of rectangular patternsPof sizen×msuch that |P|≤ (1 +ε)nm. We prove a slightly better bound in the case wherem=n, as well as constructing aperiodic SFTs of pretty low complexity. This paper is an extended version of a paper published in STACS 2020 (Kari and Moutot 12).

Abstract Nilpotent cellular automata have the simplest possible dynamics: all initial configurations lead in bounded time into the unique fixed point of the system. We investigate nilpotency in the setup of one-dimensional non-uniform cellular automata (NUCA) where different cells may use different local rules. There are infinitely many cells in NUCA but only a finite number of different local rules. Changing the distribution of the local rules in the system may drastically change the dynamics. We prove that if the available local rules are such that every periodic distribution of the rules leads to nilpotent behavior then so do also all eventually periodic distributions. However, in some cases there may be non-periodic distributions that are not nilpotent even if all periodic distributions are nilpotent. We demonstrate such a possibility using aperiodic Wang tile sets. We also investigate temporally periodic points in NUCA. In contrast to classical uniform cellular automata, there are NUCA—even reversible equicontinuous ones—that do not have any temporally periodic points. We prove the undecidability of this property: there is no algorithm to determine if a NUCA with a given finite distribution of local rules has a periodic point.

The conference series Machines, Computations and Universality (MCU) traces its roots back to mid of 1990's, and has since been concerned with gaining a deeper understanding of computation through the study of models of general purpose computation.MCU explores computation in the setting of various discrete models (Turing machines, register machines, cellular automata, tile assembly systems, rewriting systems, molecular computing models, neural models, concurrent systems, etc.) and analog and hybrid models (BSS machines, infinite time cellular automata, real machines, quantum computing, etc.).There is a particular (but not exclusive) emphasis given towards the following:

In [1] we construct aperiodic tile sets on the Baumslag-Solitar groups BS(m,n). Aperiodicity plays a central role in the undecidability of the classical domino problem on Z2, and analogously to this we state as a corollary of the main construction that the Domino problem is undecidable on all Baumslag-Solitar groups. In the present work we elaborate on the claim and provide a full proof of this fact. We also provide details of another result reported in [1]: there are tiles that tile the Baumslag-Solitar group BS(m,n) but none of the valid tilings is recursive. The proofs are based on simulating piecewise affine functions by tiles on BS(m,n).

Many undecidable questions concerning cellular automata are known to be decidable when the cellular automaton has a suitable algebraic structure. Typical situations include linear cellular automata where the states come from a finite field or a finite commutative ring, and so-called additive cellular automata in the case the states come from a finite commutative group and the cellular automaton is a group homomorphism. In this paper we generalize the setup and consider so-called group cellular automata whose state set is any (possibly non-commutative) finite group and the cellular automaton is a group homomorphism. The configuration space may be any subshift that is a subgroup of the full shift and still many properties are decidable in any dimension of the cellular space. Decidable properties include injectivity, surjectivity, equicontinuity, sensitivity and nilpotency. Non-transitivity is semi-decidable. It also turns out that the the trace shift and the limit set can be effectively constructed, that injectivity always implies surjectivity, and that jointly periodic points are dense in the limit set. Our decidability proofs are based on developing algorithms to manipulate arbitrary group shifts, and viewing the set of space-time diagrams of group cellular automata as multidimensional group shifts.

In this paper we study low-complexity colorings (or tilings) of the two-dimensional grid ℤ². A coloring is said to be of low complexity with respect to a rectangle if there exists m,n∈ℕ such that there are no more than mn different rectangular m× n patterns in it. Open since it was stated in 1997, Nivat’s conjecture states that such a coloring is necessarily periodic. Suppose we are given at most nm rectangular patterns of size n× m. If Nivat’s conjecture is true, one can only build periodic colorings out of these patterns - meaning that if the m× n rectangular patterns of the coloring are among these mn patterns, it must be periodic. The main contribution of this paper proves that there exists at least one periodic coloring build from these patterns. We use this result to investigate the tiling problem, also known as the domino problem, which is well known to be undecidable in its full generality. However, we show that it is decidable in the low-complexity setting. Finally, we use our result to show that Nivat’s conjecture holds for uniformly recurrent configurations. The results also extend to other convex shapes in place of the rectangle.

Ultimate expansivity extends concepts of expansivity and positive expansivity. We consider one-sided variants of ultimate expansivity and pseudo-orbit tracing property (also known as the shadowing property) for surjective one-dimensional cellular automata. We show that ultimately right (or left) ex pansive surjective cellular automata are chain-transitive; this improves a result by Boyle that expansive reversible cellular automata are chain-transitive. We then use this to show that left-sided pseudo-orbit tracing property and right-sided ultimate expansivity together imply pseudo-orbit tracing property for surjective cellular automata. This reproves some known results, most notably some of Nasu’s. Our result improves Nasu’s result by dropping an assumption of chain-recurrence, however, we remark that this improvement can also be achieved using the Poincaré recurrence theorem. The pseudo-orbit tracing property implies that the trace subshifts of the cellular automaton are sofic shifts. We end by mentioning that among reversible cellular automata over full shifts we have examples of right expansive cellular automata with non-sofic traces, as well as examples of cellular automata with left pseudo-orbit tracing property but non-sofic traces, illustrating that neither assumption can be dropped from the theorem mentioned above. This paper is a generalized and improved version of a conference paper presented in AUTOMATA 2018.

Abstract We study the problem of sequentializing a cellular automaton without introducing any intermediate states, and only performing reversible permutations on the tape. We give a decidable characterization of cellular automata which can be written as a single sweep of a bijective rule from left to right over an infinite tape. Such cellular automata are necessarily left-closing, and they move at least as much information to the left as they move information to the right.

[Abstract Not Available]

Cellular automata (CA) are massively parallel systems where a regular grid of finite symbols is updated according to a synchronous application of the same local update rule everywhere. A closely related concept is that of Wang tiles where a local relation between neighboring symbols determines allowed combinations of symbols in the grid. In this tutorial we start with classical results on cellular automata, such as the Garden-of-Eden theorems, the Curtis-Hedlund-Lyndon-theorem and the balance property of surjective cellular automata. We then discuss Wang tiles and, in particular, the concept of aperiodicity and the undecidability of the domino problem. The domino problem is the decision problem to determine if a given Wang tile set admits any valid tilings of the grid. We relate Wang tiles to cellular automata, and establish a number of undecidability results for cellular automata.

The tiling problem is the decision problem to determine if the infinite plane can be tiled by copies of finitely many given Wang tiles. The problem is known since the 1960’s to be undecidable. The undecidability is closely related to the existence of aperiodic Wang tile sets. There is a known metho d to construct small aperiodic tile sets that simulate iterations of one-dimensional piecewise linear functions using encodings of real numbers as Sturmian sequences. In this paper we provide details of a similar simulation of two-dimensional piecewise affine functions by Wang tiles. Mortality of such functions is undecidable, which directly yields another proof of the undecidability of the tiling problem. We apply the same technique on the hyperbolic plane to provide a strongly aperiodic hyperbolic Wang tile set and to prove that the hyperbolic tiling problem is undecidable. These results are known in the literature but using different methods.

A one-dimensional cellular automaton is a discrete dynamical system where a sequence of symbols evolves synchronously according to a local update rule. We discuss simple update rules that make the automaton perform multiplications of numbers by a constant. If the constant and the number base are selected suitably the automaton becomes a universal pattern generator: all finite strings over its state alphabet appear from a finite seed. In particular we consider the automata that multiply by constants 3 and 3/2 in base 6. We discuss the connections of these automata to some difficult open questions in number theory, and we pose several further questions concerning pattern generation in cellular automata.

The density classification task asks to design a cellular automaton that converges to the uniform configuration that corresponds to the state that is in majority in the initial configuration. We investigate connections of this problem to state-conser

We construct a cellular automaton (CA) with a sofic and mixing limit set and then construct a stable CA with the same limit set, showing there exist subshifts that can be limit sets of both stable and unstable CAs, answering a question raised by A. Maass.

Spatially scalable image coding algorithms are mostly based on linear filtering techniques that give a multi-resolution representation of the data. Reversible cellular automata can be instead used as simpler, non-linear filter banks that give similar performance. In this paper, we investigate the use of reversible cellular automata for lossy to lossless and spatially scalable coding of smooth multi-level images, such as depth maps. In a few cases, the compression performance of the proposed coding method is comparable to that of the JBIG standard, but, under most test conditions, we show better compression performances than those obtained with the JBIG or the JPEG2000 standards. The results stimulate further investigation into cellular automata-based methods for multi-level image compression.

In this work, we have designed an efficient arithmetic coder for the non-linear bi-level image coder based on reversible cellular automata transform reported in the work of Cruz-Reyes and Kari (2008). The proposed approach relies on non-linear transform operations based on RmbCA, decomposing the image into four subimages (named LL, LH, HL, HH in lexicographic order) in such a way that the LL subimage represents a low resolution version of the original image. Performing an edge detection on this subimage, it is possible to identify the coordinates where there is a high probability that the other subimages present a black pixels. In this way it is possible to minimize the amount of data that have to be processed reducing the coded bit stream. In order to increase the probability that black pixels lie in the selected region, the coding algorithm enlarges the identified region according to the values of Sobel operators computed on the LL subimage.

Self-assembly, the process by which objects autonomously come together to form complex structures, is omnipresent in the physical world. Recent experiments in self-assembly demonstrate its potential for the parallel creation of a large number of nanostructures, including possibly computers. A systematic study of self-assembly as a mathematical process has been initiated by L. Adleman and E. Winfree. The individual components are modeled as square tiles on the infinite two-dimensional plane. Each side of a tile is covered by a specific “glue,” and two adjacent tiles will stick iff they have matching glues on their abutting edges. Tiles that stick to each other may form various two-dimensional “structures” such as squares and rectangles, or may cover the entire plane. In this paper we focus on a special type of structure, called a ribbon: a non-self-crossing rectilinear sequence of tiles on the plane, in which successive tiles are adjacent along an edge and abutting edges of consecutive tiles have matching glues. We prove that it is undecidable whether an arbitrary finite set of tiles with glues (infinite supply of each tile type available) can be used to assemble an infinite ribbon. While the problem can be proved undecidable using existing techniques if the ribbon is required to start with a given “seed” tile, our result settles the “unseeded” case, an open problem formerly known as the “unlimited infinite snake problem.” The proof is based on a construction, due to R. Robinson, of a special set of tiles that allow only aperiodic tilings of the plane. This construction is used to create a special set of directed tiles (tiles with arrows painted on the top) with the “strong plane-filling property”—a variation of the “plane-filling property” previously defined by J. Kari. A construction of “sandwich” tiles is then used in conjunction with this special tile set, to reduce the well-known undecidable tiling problem to the problem of the existence of an infinite directed zipper (a special kind of ribbon). A “motif” construction is then introduced that allows one tile system to simulate another by using geometry to represent glues. Using motifs, the infinite directed zipper problem is reduced to the infinite ribbon problem, proving the latter undecidable. An immediate consequence of our result is the undecidability of the existence of arbitrarily large structures self-assembled using tiles from a given tile set.

Self-assembly, the process by which objects autonomously come together to form complex structures, is omnipresent in the physical world. A systematic study of self-assembly as a mathematical process has been initiated. The individual components are modelled as square tiles on the infinite two-dimensional plane. Each side of a tile is covered by a specific "glue", and two adjacent tiles will stick if they have matching glues on their abutting edges. Tiles that stick to each other may form various two-dimensional "structures" such as squares, rectangles, or may cover the entire plane. In this paper we focus on a special type of structure, called ribbon: a non-self-crossing sequence of tiles on the plane, in which successive tiles are adjacent along an edge, and abutting edges of consecutive tiles have matching glues. We prove that it is undecidable whether an arbitrary finite set of tiles with glues (infinite supply of each tile type available) can be used to assemble an infinite ribbon. The proof is based on a construction, due to Robinson (1971), of a special set of tiles that allow only aperiodic tilings of the plane. This construction is used to create a special set of directed tiles (tiles with arrows painted on the top) with the "strong plane filling property" - a variation of the "plane filling property" previously defined by Kari (1990, 1994). A construction of "sandwich" tiles is then used in conjunction with this special tile set, to reduce the well-known undecidable tiling problem to the problem of the existence of an infinite directed zipper (a special kind of ribbon). A "motif" construction is then introduced that allows one tile system to simulate another by using geometry to represent glues. Using motifs, the infinite directed zipper problem is reduced to the infinite ribbon problem, proving the latter undecidable. The result settles an open problem formerly known as the "unlimited infinite snake problem". Moreover, an immediate consequence is the undecidability of the existence of arbitrarily large structures self-assembled using tiles from a given tile set.

We study the family of structurally reversible cellular automata that use the (generalized) Margolus neighborhoods. We show that every reversible cellular automaton (RCA) can be embedded into the standard two layer Margolus neighborhood defined by tw

A new motion compensation technique that allows more than one motion vector inside each block is introduced. The technique uses the intensity information to determine which motion vector to apply at any given pixel. An efficient motion estimation algorithm is described that finds near optimal selections of motion vectors. The simulation results show a significant improvement in the prediction accuracy over the traditional one motion vector per block model.

This paper describes Iterated Systems' submission to the MPEG-4 committee in January 1996. A system for compressing video is presented which expresses predictive frames of a sequence by means of motion vectors applied to variable-size blocks with a constant intensity adjustment. The motion vectors are organized into a partial quadtree, which allows incomplete splitting of blocks into zero to four quadrants. The motion vectors, mean intensity offsets, and partial quadtree structure are arrived at by a joint optimization process which may be carried out in a bottom-up fashion. A form of generalized overlapped block motion compensation applicable at all block sizes is presented, and a method for encoding segmented video is shown. The performance of the algorithm is compared with that of Telenor's H.263 for three of the MPEG-4 test sequences which show that the former is comparable or superior to the latter for low bit rates.

The lower bounds on communication complexity measures of language generation by Parallel Communicating Grammar Systems (PCGS) are investigated. The first result shows that there exists a language that can be generated by some dag-PCGS (PCGS with communication structures realizable by directed acyclic graphs) consisting of 3 grammars, but by no PCGS with tree communication structure. The second result shows that dag-PCGS have their communication complexity of language generation either constant or linear.

Weighted finite automata (WFA) is a tool for specifying real functions and in particular grayscale images. The image compression software based on this algorithm is competitive with other methods in compression of typical grayscale images. It performs particularly well for high compression rates, for color images, and compared to other methods it has several additional advantages. This paper mainly deals with image manipulation. Weighted finite transducers (WFT) can be used to specify the widest variety of image transformations (linear operators on grayness functions). The authors briefly introduce WFA and WFT and give some examples of image transformations specified by WFT.

The limit set of a celullar automaton consists of all the configurations of the automaton that can appear after arbitrarily long computations. It is known that the limit set is never empty—it contains at least one homogeneous configuration. A CA is called nilpotent if its limit set contains just one configuration. The present work proves that it is algorithmically undecidable whether a given one-dimensional cellular automaton is nilpotent. The proof is based on a generalization of the well-known result about the undecidability of the tiling problem of the plane. The generalization states that the tiling problem remains undecidable even if one considers only so-called NW-deterministic tile sets, that is, tile sets in which the left and upper neighbors of each tile determine the tile uniquely. The nilpotency problem is known to be undecidable for d-dimensional CA for $d \geq 2$. The result is the basis of the proof of Rice’s theorem for CA limit sets, which states that every nontrivial property of limit sets is undecidable.