Pierre Guillon
email: pierre.guillon@univ-mlv.fr

Gaétan Richard
email: gaetan.richard@lif.univ-mrs.fr

Nilpotency and Limit Sets of Cellular Automata ⋆

Keywords: cellular automata, nilpotency, dynamical systems, attractors

A one-dimensional cellular automaton is a dynamical system which consisting in a juxtaposition of cells whose state changes over discrete time according to that of their neighbors. One of its simplest behaviors is nilpotency: all configurations of cells are mapped after a finite time into a given "null" configuration. Our main result is that nilpotency is equivalent to the condition that all configurations converge towards the null configuration for the Cantor topology, or, equivalently, that all cells of all configurations asymptotically reach a given state.

Introduction

Discrete dynamical systems aim at representing evolutions of objects in astronomy, chemistry, cellular biology, zoology, computing networks. . . Evolutions of these objects can often be described by iterations of a continuous function. The sequence of values obtained is called orbit.

A long-standing issue in dynamical systems is the distinction between limit behavior and finitely-reached behavior: in which case does convergence of orbits imply reaching the limit in finite time? Of course, there are obvious examples in which all orbits converge towards the same limit without ever reaching it, such as the division by 2 on segment [0, 1].

Here, we limit our study to some particular systems: cellular automata (CA). A CA consists in an infinite number of identical cells arranged on a regular lattice. All cells evolve synchronously according to their own state and those of their neighbors. It is thus a dynamical system on the set of configurations (which map each cell of the lattice to some state).

Endowing the set of configurations with the product topology allows the following restatement of the above-mentioned issue: in which case can local behavior (evolution of a particular cell) be uniformed into global behavior (evolution of the whole configuration)? This question can also be seen as a comparison between the limit set (configurations that can be reached arbitrarily late) and the ultimate set (adjacent values of orbits).

In this article, we study in detail the nilpotency of CA, in which all configurations eventually reach a given uniform configuration. Even though it represents the simplest behavior a dynamical system can have, its relevance grew in the CA field when Jarkko Kari made it the prototype of the undecidable problem on dynamics of CA [START_REF] Kari | The nilpotency problem of one-dimensional cellular automata[END_REF], which has been widely used in reductions since then. This paper is dedicated to the equivalence between nilpotency and convergence toward a given configuration, or nilpotency of the trace subshift, which is a dynamical system linked to the CA, studied in [START_REF] Cervelle | Sofic trace of a cellular automaton[END_REF][START_REF] Cervelle | Towards a Rice theorem on traces of cellular automata[END_REF], and which represents the observation of the evolution of a cell by a fixed observer. In other words, in that case, the local behavior can be uniformed.

The restriction to the case of CA with a spreading state is simpler and was already useful in some reductions (see for instance [START_REF] Cervelle | Towards a Rice theorem on traces of cellular automata[END_REF]). Here, we extend the result to all one-dimensional CA.

Section 2 is devoted to definitions and preliminary results. In Sect. 3, we recall some results about the nilpotency, and prove that uniform configurations are isolated in the limit set only if the CA is nilpotent. Sect. 4 is devoted to proving our new characterization of nilpotency and Sect. 5 gives some new tracks of generalization.

Preliminaries

Let N * = N \ {0}. For i, j ∈ N with i ≤ j, [i, j] (resp. ]i, j[) denotes the set of integers between i and j inclusive (resp. exclusive). For any function F from A Z into itself, F n denotes the n-fold composition of F with itself.

Words. Let A be a finite alphabet with at least two letters. A word is a finite sequence of letters w = w 0 . . . w |w|-1 ∈ A * , where |w| is the length of w. A factor of a word w = w 0 . . . w |w|-1 ∈ A * is a word w [i,j] = w i . . . w j , for 0 ≤ i ≤ j < |w|.

Dynamical systems

A (discrete) dynamical system (DS for short) is a couple (X, F ), where X is a compact metric space, and F is a continuous function. When no confusion is possible (especially when X = A Z ), X will be omitted. The orbit of initial point x ∈ X is the sequence of points F j (x) when generation j ∈ N grows (where F j denotes the j-fold composition of F with itself). We note

O F (x) = F j (x) j ∈ N . We say that Y ⊂ X is F -stable and that (Y, F ) is a subsystem of (X, F ) if F (Y ) ⊂ Y .
Asymptotic behavior of orbits is represented by two particular sets:

the (Ω-) limit set of a DS (X, F ) is the set Ω F = j∈N F j (X) of all configurations that can appear arbitrarily late in orbits.

-The ultimate set is the set ω F = x∈X J∈N O F (F J (x)) of all adhering values of orbits.

One can notice that both are F -stable sets, and that, by definition, ω F ⊂ Ω F , whereas the converse is generally false. Moreover, compactness implies the nonemptiness of those two sets, and that the limit and ultimate sets of any DS F are equal to those of any of its iterated F k for k ∈ N * .

Space A Z

Let A be a finite alphabet. The set A Z (resp. A N ) is the set of bi-infinite (resp. infinite) sequences over alphabet A. An element x ∈ A Z is called configuration (see Fig. 1a). A factor of x is a word x [i,j] = x i . . . x j , for i ≤ j. This notion of factor can be extended to infinite intervals (such as ] -∞, j] or [i, +∞[). The notation x <i> stands for the central factor x [-i,i] .

Topology. A Z is endowed with the product (or Cantor ) topology, corresponding to the distance

d : A Z × A Z → R + (x, y) → 2 -min x i =y i |i| ,
which makes it compact, perfect, totally disconnected. A similar distance can be defined on A N . An example of two configuration at distance 2 -2 is depicted in Fig. 1b. Cylinders. For j, k ∈ N and a finite set W of words of length j, we note

[W ] k the set x ∈ A Z x [k,k+j[ ∈ W . Such a set is called a cylinder. Cylinders form a countable base of clopen sets. We note [W ] k C the complement of the cylinder [W ] k , [W ] the center cylinder [W ] ⌊ j 2 ⌋ , if K ⊂ A N , [W ] k K = x ∈ A Z x [k,k+j[ ∈ W and x [k+j,∞[ ∈ K , and, if K ⊂ A -N , K[W ] k = x ∈ A Z x [k,k+j[ ∈ W and x ]-∞,k[ ∈ K .
Similarly to what is done for languages, we will assimilate a singleton with its unique element; for instance, z[u] i z ′ will denote the configuration

x ∈ A Z such that x ]-∞,i[ = z, x [i,i+|u|[ = u and x ]i+|u|,∞[ = z ′ . Finally, note that notations such as z[]z ′ will be used for the configuration x ∈ A Z such that x ]-∞,0[ = z and x [0,∞[ = z ′ .
Finite configurations. If q ∈ A, then q ω is the infinite word of A N consisting in periodic repetitions of q, ω q ω is the (spatially) periodic configuration of A Z consisting in repetitions of q, ω q ω is the q-uniform configuration, and any configuration ω q[u]q ω , where u ∈ A * , is a q-finite configuration. A q-semi-finite configuration is a configuration x = ω qz for some z ∈ A N \{q ω }. Note that the set of q-finite configurations is dense, since any finite word u can be extended as ω quq ω ∈ [u].

Cellular automata

A (one-dimensional two-sided) cellular automaton (CA for short) is a discrete dynamical system consisting in cells distributed over the regular lattice Z. Each cell i ∈ Z of the configuration x ∈ A Z has a state x i in the finite alphabet A. That state evolves according to the state of their neighbors:

F (x) i = f (x [i-r,i+r[ ))
, where f : A 2r+1 → A is the local rule and r ∈ N the radius of the CA. By abuse of notation, we assimilate the CA to its global function F : A Z → A Z , which is a DS on the configurations space. Usually, an orbit is graphically represented by a two-dimensional space-time diagram, such as in Figure 2.

Example 1. A simple example of CA is the min CA, defined on alphabet A = {0, 1} by radius 1 and local rule f :

A 3 → A (x -1 , x 0 , x 1 ) → 1 if x -1 = x 0 = x 1 = 1 0 otherwise .
The typical evolution makes all finite bunches of 1s disappear progressively; only the infinite configuration ω 1 ω will not lose any 1 and nearly all configurations tend towards ω 0 ω . The ultimate set is ω F = { ω 0 ω , ω 1 ω } and the limit set Ω F is the set of configurations that do not contain patterns of the form 10 k 1 for any k ∈ N * . Quiescent states. A state 0 ∈ A is said to be quiescent for the CA F with local rule f if f (0, . . . , 0) = 0. Equivalently, F ( ω 0 ω ) = ω 0 ω , which is called a quiescent uniform configuration. For instance, both 0 and 1 are quiescent states for the min CA. We can see that the set of uniform configurations form a finite, hence ultimately periodic, subsystem of the cellular automaton; hence ∀a ∈ A, ∃j < |A| , F |A| ( ω a ω ) = F |A|-j-1 ( ω a ω ), which gives the following remark: Remark 1. For any CA F , F j admits a quiescent state for some j ∈ [1, |A|].

It can also easily be seen that the ultimate set of any CA contains all quiescent configurations. Since ω F j = ω F , the previous remark gives, in particular, that for any CA F , there is at least one uniform configuration in ω F (and therefore Ω F ).

Blocking words. A word

w ∈ A * is (i, k)-blocking (or simply k-blocking) for CA F : A Z → A Z if ∀x, y ∈ [w] -i , ∀j ∈ N, F j (x) [0,k[ = F j (y) [0,k[ . If r is the radius of F , note that if a word w is (i, r)-blocking, and x ∈ [w] -i , then for all configurations y ∈ A Z such that y [-i,∞[ = x [-i,∞[ (resp. y ]-∞,|w|-i[ = x ]-∞,|w|-i[ ),
and for all generation j ∈ N, we have

F j (y) [0,∞[ = F j (x) [0,∞[ (resp. F j (y) ]-∞,r[ = F j (x) ]-∞,r[ ),
i.e. information cannot pass through an rblocking word. For instance, in the min CA, the word 0 is (0, 1)-blocking, since ∀x ∈ [0], ∀j ∈ N, F j (x) 0 = 0 (see Fig. 2), hence space-time diagrams containing one 0 can be separated into two independent evolutions.

Symbolic dynamics

The shift map σ : A Z → A Z is a particular CA defined by σ(x) i = x i+1 for every x ∈ A Z and i ∈ Z which shifts configurations to the left. Hedlund [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF] has shown that cellular automata are exactly the DS on A Z which commute with the shift.

This characterization leads us to study shift-invariant subsets of A Z , among which, for instance, the image or limit sets of any CA. With the help of topology, we shall give some useful properties on those sets.

Subshifts. The one-sided shift (or simply shift when no confusion is possible), also noted σ by abuse of notation, is the self-map of A N such that σ(z) i = z i+1 , for every z ∈ A N and i ∈ N. A one-sided subshift Σ ⊂ A N is a σ-stable closed set of infinite words. The following statements concern a two-sided version of subshifts.

Proposition 1. The only closed shift-stable subset of

A Z of nonempty interior is A Z .
Proof. Let Σ be such a set. Having nonempty interior, it must contain some cylinder [u] i with u ∈ A * and i ∈ Z. Being closed and shift-stable, it must also

contain j≤i σ j ([u] i ) = A Z . ⊓ ⊔ Corollary 1. If A Z = j∈N Σ j
where the Σ j are closed and shift-stable, then A Z is equal to some Σ j0 .

Proof. A Z being complete, and of nonempty interior, the Baire Theorem states for some j 0 ∈ N, Σ j0 has nonempty interior too. By Proposition 1, Σ j0 = A Z . ⊓ ⊔

Trace

Rather than observing the whole configuration, trace consists in observing a specific portion of configuration during evolution of a cellular automaton. This notion establishes a link between the theory of cellular automata and symbolic dynamics.

Definition 1 (Trace). Given a CA F , the trace of F with initial condition

x ∈ A Z is T F (x) = (F j (x) 0 ) j∈N .
In other words, it is the central column of the space-time diagram of initial configuration x (see Figure 3). The trace subshift of F is the image set τ F = T F (A Z ). Similarly, we define T k F (x) = (F j (x) [0,k[ ) j∈N , the sequence of the words at positions in [0, k[ in the space-time diagram of initial configuration x, and τ k F = T k F (A Z ). For instance, if A = {0, 1}, then the trace subshift is (0 + 1) ω for the shift, 0 ω + 1 ω for the identity and (0 + 1)0 ω for the CA that maps every cell to 0 (see [START_REF] Cervelle | Sofic trace of a cellular automaton[END_REF] for more examples).

Note that T F F = σT F and, as T F is continuous, we say it is a factorization between the CA and the subshift (τ F , σ) which means that their two dynamics are very closely related. For more about factorizations, see [START_REF] Kůrka | Topological and symbolic dynamics[END_REF]. In the following, τ F and τ k F may stand for the dynamical systems (τ F , σ) and (τ k F , σ). In this paper, we try to obtain links between the set of possible traces and the global behavior of the cellular automaton. That is try to "globalize" a local observation of the behavior.

Nilpotent cellular automata

In this section, we recall the definition and characterizations of cellular automata nilpotency, and its known link with the limit set. We present a short proof empha-sizing on the fact that a CA is nilpotent as soon as some uniform configuration is isolated in its limit set. Definition 2. A DS (X, F ) is weakly nilpotent if there is a particular "null" configuration z ∈ X such that for every point x ∈ X, there is a generation J ∈ N such that ∀j > J, F j (x) = z. The system is said nilpotent if the generation J does not depend on the point, i.e. ∃J ∈ N, ∀x ∈ X, ∀j > J, F j (x) = z.

Let us now consider the specific case of cellular automata. If a CA F is weakly nilpotent, then, from the definition, the null configuration must be Finvariant. Moreover, for any z ∈ A Z , there is some j for which, on the one hand F j (σ(z)) = z, and on the other hand, F j (σ(z)) = σ(F j (z)) = σ(z). Hence z = σ(z) is a uniform quiescent configuration, i.e. z = ω 0 ω for some quiescent state 0. One can also make the following easy remarks:

Remark 2.
-Suppose F is a CA and j ∈ N a generation such that for all configurations x ∈ A Z , F j (x) 0 = 0. Then shift-invariance of A Z gives A Z = k∈Z σ k F -j ([0]), and by commuting F and the shift, we obtain

A Z = F -j ( ω 0 ω ). Hence F is nilpotent. -On the other hand, if F is not nilpotent, then F -j ([0 C ]) is a nonempty
open set; in particular, it contains some q-finite configurations, for any state q ∈ A. -Note that if F is a non-nilpotent CA, from Remark 1, there is some J ∈ N such that some 0 ∈ A is quiescent for F J . We can see that the set of 0-finite configurations is F J -stable. Hence, from the previous point, for all j ∈ N, F j (A Z ) contains some non-uniform 0-finite configuration z = ω 0[u]0 ω with u ∈ A * and z 0 = 0.

Here is a precise characterization of the limit set of nilpotent CA.

Theorem 1 ( Čulik, Pachl, Yu [START_REF] Čulik | On the limit sets of cellular automata[END_REF]). A CA whose limit set is a singleton is nilpotent.

Proof. If F is a CA such that Ω F ∩[0 C ] = ∅, the intersection j∈N (F j (A Z )∩[0 C ]) of closed sets is empty. By compactness, F j (A Z ) ∩ [0 C ] is empty for some j ∈ N. F j (A Z ) being a subshift, we conclude that F j (A Z ) ∩ ( i∈Z [0 C ] i ) = F j (A Z )\ ω 0 ω is empty. ⊓ ⊔
With this characterization and the fact that Ω F = Ω F j , we have the following corollary.

Corollary 2. A CA F is nilpotent if and only if so is some (so are all) of its iterated CA F n , for n ∈ N.

⊓ ⊔

The next allows to prove the well-known equivalence between nilpotency and weak nilpotency.

Proposition 2. If for every configuration

x ∈ A Z , there is a generation j ∈ N and a cell i ∈ Z such that F j (x) [i,∞[ = 0 ω (resp. F j (x) ]-∞,i] = ω 0), then F is nilpotent. Proof. Assume A Z = j∈Ni∈Z σ i (F -j ( ω A[0 ω )) (the other case is symmetric). From Corollary 1, A Z = σ i (F -j ( ω A[0 ω
)) for some generation j ∈ N and some i ∈ Z. In particular, σ i (A Z ) = F -j ([0]), and Remark 2 allows to conclude the claim.

⊓ ⊔

Corollary 3. A weakly nilpotent CA is nilpotent. ⊓ ⊔

There is indeed some "gap" between the possible evolutions of nilpotent and non-nilpotent CA. This is also stressed by the following result on limit set: it is sufficient that the it admits an isolated uniform configuration for the CA to be nilpotent. Proposition 3. If F is a non-nilpotent CA, then Ω F contains some semi-finite configuration ω 0[]z, for some 0 ∈ A and some z ∈ A N \{0 ω }.

Proof. Let F be a non-nilpotent CA. Should we iterate it, we can suppose it has a quiescent state 0 ∈ A, thanks to Remark 1 and Corollary 2. By Remark 2, for every generation j ∈ N, F j (A Z ) ∩ ω 0[0 C ] = ∅, and compactness gives that

Ω F ∩ ω 0[0 C ] = ∅.
⊓ ⊔ Theorem 2. The limit set of any non-nilpotent CA does not have any isolated uniform configurations.

Proof. Let F a non-nilpotent CA, 0 ∈ A, k ∈ N and x ∈ ω 0[] ∩ Ω F \{ ω 0 ω } as in Proposition 3. Then, for any k ∈ N, σ -k (x) is a configuration of Ω F distinct from ω 0 ω , and which is in the cylinder [0 2k+1 ] around ω 0 ω .

⊓ ⊔

Remark that, on the contrary, ω F can have isolated uniform configurations even in the non-nilpotent case. For instance, the ultimate set of the min CA is

{ ω 0 ω , ω 1 ω }.
The previous result allows state that limit sets are either a singleton or infinite.

Corollary 4 ( Čulik, Pachl, Yu [START_REF] Čulik | On the limit sets of cellular automata[END_REF]). The limit set of any non-nilpotent CA is infinite. ⊓ ⊔ Note that the limit set can be numerable, as for the min CA, or innumerable, as for the shift CA. To sum up, the limit set of a CA has a very precise structure, and, as will be seen more deeply in the following section, constraining a little can make it collapse to a singleton, i.e. make the CA nilpotent.

We have seen in the previous section that there is a "gap" between nilpotent and non-nilpotent CA in terms of the limit set. The aim of this section is to prove that it is also the case for the ultimate set, or, equivalently, for the trace subshift: a constraint such as the ultimate set being a singleton is restrictive enough to imply nilpotency. We first give a directly proved characterization of that notion for trace subshifts.

Remark 3. Similarly to the case of CA, we can notice that a subshift Σ ∈ A N is weakly nilpotent if and only if there is some state 0 ∈ A such that for every infinite word w ∈ Σ, there is some j ∈ N such that w [j,∞[ = 0 ω . The previous remark will justify the concept of 0-nilpotency, where 0 is a quiescent state. We also say that some configuration x is 0-mortal for the CA F if there exists j ∈ N such that F j (x) = 0 ω . Proposition 4. Let F a CA. The following statements are equivalent:

1. τ F is weakly 0-nilpotent. 2. τ k F is weakly 0 k -nilpotent, for any integer k ∈ N * . 3. For every configuration x ∈ A Z , F n (x) tends, as n → ∞, to the same "null" configuration ω 0 ω . 4. ω F = { ω 0 ω }. ⊓ ⊔
Let us prove now that, in the same way as weakly nilpotent CA are nilpotent, weakly nilpotent traces are nilpotent, i.e. the corresponding CA is nilpotent (at least in dimension 1).

The proof is organized the following way: we first prove that a CA with weakly nilpotent trace has an r-blocking word, and then that there exists a bound on the converging time for mortal finite configurations. At last, we exhibit a contradiction with a non-nilpotency hypothesis. Lemma 1. Let F a CA whose trace is weakly 0-nilpotent; then for every k ∈ N, there is a generation J ∈ N such that for every configuration

x ∈ A Z , ∃j ≤ J, F j (x) ∈ [0 k ].
Proof. Let F a CA such that τ F is weakly nilpotent and k ∈ N. By Point 2 of Proposition 4 and Remark 3, we have

A Z = j∈N F -j ([0 k ]). By compactness, we can extract a finite covering A Z = j≤J F -j ([0 k ]) for some J ∈ N. ⊓ ⊔ Lemma 2.
If F is a CA with a nilpotent trace, then it admits an r-blocking word.

Proof. Let F such a CA. By Point 2 of Proposition 4, A Z = J∈N j>J F -j ([0 r ]) has nonempty interior, for some 0 ∈ A; hence the Baire Theorem states that there is some J ∈ N for which j>J F -j ([0 r ]) has nonempty interior; it contains a cylinder [u] -i for some u ∈ A * and i ∈ N. We can assume without loss of generality that i ≥ Jr and |u| ≥ (J + 1)r + i, which gives ∀x, y ∈ [u] -i , ∀j ≤ J, F j (x) [0,r[ = F j (y) [0,r[ , and we already have by construction that ∀x, y ∈ [u] -i , ∀j > J, F j (x) [0,r[ = 0 r = F j (y) [0,r[ . Hence, u is an (i, r)-blocking word. ⊓ ⊔ Lemma 3. Let F a CA whose trace is weakly 0-nilpotent; then there is a generation j for which any 0-finite 0-mortal configuration x satisfies F j (x) = ω 0 ω .

Proof. Consider F a CA such that τ F is weakly nilpotent, and for all j ∈ N, there is a finite mortal configuration y such that F j (y) = ω 0 ω . Should it be shifted, we can suppose F j (y) 0 = 0.

Claim. For every k ∈ N, there is a 0-finite 0-mortal configuration y ∈ [0 2k+1 ] and a generation j ≥ k such that F j (y) 0 = 0.

Proof. Let k ∈ N. From Lemma 1, ∃J ∈ N, ∀y ∈ A Z , ∃j ≤ J, F j (y) ∈ [0 2k+1 ]. By hypothesis, there exists a finite mortal configuration x for which F J (x) 0 = 0. Hence, ∃j ≤ J, F j (x) ∈ [0 2k+1 ]. Just take the configuration y = F j (x); we have F J-j (y) 0 = F J (x) 0 = 0. Of course, ∀j < k, F j (y) 0 = 0.

⊓ ⊔

Claim. Let x a 0-finite 0-mortal configuration and k ∈ N. Then, there is a 0-finite 0-mortal configuration y ∈ [x <rk> ] and

j ∈ N F j (y) 0 = 0 j ∈ N F j (x) 0 = 0 .
Proof. Let x a finite configuration and n ∈ N such that F n (x) = ω 0 ω . Should we take a larger k, we can assume that x ∈ ω 0[A 2r(k-2n) ]0 ω . In particular, note that k ≥ 2n. By the previous claim, there exists a finite mortal configuration x ′ ∈ [0 2k+1 ] and a generation j ≥ k such that F j (x) 0 = 0. Let

y = x ′ ]-∞,-rk[ [x <rk> ]x ′
]rk,∞[ . We can easily see by induction on j ≤ n that

F j (y) ∈ F j (x ′ ) ]-∞,-r(k-2n+j)[ [A 2rj F j (x) <r(k-j)> A 2rj ]F j (x ′ ) ]r(k-2n+j),∞[ . In particular, on the one hand, j ∈ N F j (y) 0 = 0 ∩[0, n] = j ∈ N F j (x) 0 = 0 ∩ [0, n] = j ∈ N F j (x) 0 = 0 . On the other hand, since F n (x) <r(k-n)> = 0 2r(k-n) = F n (x ′ ) <r(k-n)> , we get F n (y) = F n (x ′ ). By construction, there is a generation j ≥ k > n such that F j (y) 0 = F j (x ′ ) 0 = 0. To sum up, j ∈ N F j (y) 0 = 0 j ∈ N F j (x) 0 = 0 . ⊓ ⊔
We can now build by induction a sequence (y k ) k∈N of finite mortal configurations, with x 0 = ω 0 ω , and such that for k ∈ N, x k+1 ∈ [x k <r(k+1)> ] and j ∈ N F j (x k+1 ) 0 = 0 j ∈ N F j (x k ) 0 = 0 . That Cauchy-Bolzano sequence of finite mortal configurations tends to some configuration x ∈ A Z such that j ∈ N F j (x) 0 = 0 is infinite (by continuity of the trace), i.e. τ F is not nilpotent.

⊓ ⊔ Lemma 4. Let F a one-dimensional non-nilpotent CA admitting a weakly 0nilpotent trace and an r-blocking word. Then for every generation j ∈ N, there exists some 0-finite 0-mortal configuration y such that F j (y) = ω 0 ω .

Proof. Let F such a CA, u a (i, r)-blocking word and j ∈ N. By blockingness and Point 2 of Proposition 4, there is a generation k ∈ N such that ∀n ≥ k, ∀z ∈ [u] -i , F n (z) ∈ [0 r ] 0 . Should we take a strict superword for u, we can assume |u| = 2i + 1. Remark 2 states that there is some finite configuration x such that F j+k (x) 0 = 0. Consider the configuration x ′ = ω 0[ux <r(j+k)> u]0 ω , and the configuration y = ω 0[F k (x ′ ) <r(j+k)+i> ]0 ω . By construction, F j (y) 0 = F j+k (x) 0 = 0. By induction on the generation n ∈ N, F n+k (x ′ ) ∈ [0 r A 2r(j+k)+2i+1 0 r ], and thus F n (y) ∈ ω 0[A 2r(j+k)+2i+1 ]0 ω . By hypothesis and Point 2 of Proposition 4, there is some generation l ∈ N such that F l (y) ∈ [0 2r(j+k)+2i+1 ], which gives Proof. Suppose there is a non-nilpotent CA F such that τ F is nilpotent. Then, by Lemma 2, we know that there exists an r-blocking word. Lemmas 4 and 3 give a contradiction. ⊓ ⊔ Corollary 5. The subshift (ε + 0 * 1)0 ω is not the trace of any one-dimensional CA. ⊓ ⊔

F l (y) = ω 0 ω . ⊓ ⊔ 0 ω 0 ω u x <r(j+k)> u k j F k (x ′ ) <r (

Conclusion

To sum up, for a one-dimensional CA F , the following statements are equivalent:

F is nilpotent ⇔ F is weakly nilpotent ⇔ τ k F is nilpotent ⇔ τ k F is weakly nilpotent ⇔ Ω F is finite
⇔ Ω F has some isolated uniform configuration ⇔ Ω F is a singleton ⇔ ω F is a singleton We can remark that the nilpotency of a CA associated to a local rule does not depend on the anchor. Hence, all characterizations work up to a shift of the rule.

The main open question is of course the generalization of these result to CA in upper dimensions (configurations in A Z d , d > 1). Juxtaposing blocking words (Lemma 4) is the crucial part which is difficult to transpose in dimension 2.

Another one is whether it is sufficient to take as a hypothesis that all orbits have ω 0 ω as an adhering value, instead of a limiti.e. all space-time diagrams walk through cylinders [0 k ] for any k ∈ N -to conclude the CA is nilpotent.

A natural question is whether the characterization of nilpotency in terms of trace can be generalized, for instance to preperiodicity (i.e. ultimate periodicity), in the same way as the finite-time characterization of nilpotency (Corollary 3; see for instance [START_REF] Kůrka | Topological and symbolic dynamics[END_REF]). This is untrue; some CA F may have all the infinite words of its trace preperiodic (i.e. ∀z ∈ τ F , ∃p, q ∈ N, σ p+q (z) = σ q (z)), but with an unbounded preperiod, such as the min CA, whose trace subshift 1 ω + 1 * 0 ω has only preperiodic words, but with an arbitrarily high preperiod.

Note that our result can be seen as a constraint on the structure of limit sets of non-nilpotent CA. In that idea, Proposition 3 allows to state that a CA is nilpotent as soon as its limit set contains only periodic configurations. Note that this is untrue for ω F : for instance, the min CA has only spatially periodic configurations in its ultimate set. We can also mention another misleadingly simple issue, which concerns the presence of infinite configurations. Conjecture 1. If F is a CA and 0 ∈ A such that Ω F contains only 0-finite configurations, then F is 0-nilpotent.

Fig. 1 .

 1 Fig. 1. Elements of A Z

Fig. 2 .

 2 Fig. 2. A space-time diagram of the min CA with highlighted r-blocking word.

0Fig. 3 .

 3 Fig. 3. Trace seen on the space-time diagram

Fig. 4 .Theorem 3 .

 43 Fig. 4. Construction of mortal finite configurations with arbitrary slow convergence

Acknowledgement

We gratefully thank Guillaume Theyssier, François Blanchard, Jarkko Kari for our very profitable discussions on that matter. Thanks also to our referees, who criticized constructively a rather unrefined version.

⋆ This work has been supported by the ANR Blanc "Projet Sycomore".


Julien Cervelle
email: julien.cervelle@univ-mlv.fr

Pierre Guillon
email: pierre.guillon@univ-mlv.fr

Towards a Rice Theorem on Traces of Cellular Automata ⋆

Keywords: discrete-time dynamical systems, cellular automata, symbolic dynamics, formal languages, computability, decidability

The trace subshift of a cellular automaton is the subshift of all possible columns that may appear in a space-time diagram. We prove the undecidability of a rather large class of problems over trace subshifts of cellular automata.

Introduction

Cellular automata are well-known formal models for complex systems. They are used in a huge variety of different scientific fields including mathematics, physics and computer science.

A cellular automaton (CA for short) consists in an infinite number of identical cells arranged on a regular lattice. All cells evolve synchronously according to their own state and those of their neighbors.

Despite the apparent simplicity of the definition of the system, one can observe very complex behaviors. Many attempts have been made to classify them: strictly in topological terms [START_REF] Gilman | Classes of linear automata[END_REF], emphasizing limit sets [START_REF] Hurley | Attractors in cellular automata[END_REF], considering computability [START_REF] Mazoyer | Inducing an order on cellular automata by a grouping operation[END_REF], or yet studying the language appearing in cell evolution [START_REF] Kůrka | Languages, equicontinuity and attractors in cellular automata[END_REF]. Most behaviors have been proved undecidable: concerning the attractors (nilpotency in [START_REF] Kari | The nilpotency problem of one-dimensional cellular automata[END_REF], other properties in [START_REF] Kari | Rice's theorem for the limit sets of cellular automata[END_REF]), the equicontinuity classification [START_REF] Durand | On undecidability of equicontinuity classification for cellular automata[END_REF], or universality [START_REF] Ollinger | The intrinsic universality problem of one-dimensional cellular automata[END_REF].

Our approach concerns the languages that can be associated to a CA and especially the trace subshift which is the set of all possible sequences of the states a particular cell takes during the evolution. Motivations come both from classical symbolic dynamics but also from physics. Indeed, when observing natural phenomena due to physical constraints, one can keep trace only of a finite number of measurements. This set of measurements takes into account only a minor part of the parameters ruling the phenomenon under investigation. Hence, to some extent, what is observed is the "trace" of the phenomenon left on the instruments.

We try to prove a "Rice Theorem" for trace subshifts, similarly to what is done in [START_REF] Kari | Rice's theorem for the limit sets of cellular automata[END_REF][START_REF] Cervelle | Tilings: recursivity and regularity[END_REF] for limits sets and tilings, that is to say the undecidability of non-trivial properties over the trace subshift given a CA.

The paper is organized as follows. Section 2 to 4 are devoted to definitions and main concepts of the paper. Section 5 study the case of a Rice theorem for a simpler definition of trace called "subtrace". Section 6 extends the result to the "trace" case.

Definitions

Let N * = N\{0}. For i, j ∈ N with i ≤ j, [i, j] denotes the set of integers between i and j inclusive. For any function F from A Z into itself, F n denotes the n-fold composition of F with itself.

Languages. Let A be a finite alphabet with at least two letters. A word is a finite sequence of letters w = w 0 . . . w |w|-1 ∈ A * . A factor of a word w = w 0 . . . w |w|-1 ∈ A * is a word w [i,j] = w i . . . w j , for 0 ≤ i ≤ j < |w|. We note w [i,j] ⊏ w. A language on alphabet A is a set of words on alphabet A. Given two languages C, D ⊂ A * , CD denotes their concatenation, When no confusion is possible, given a word w, we also note w the language {w}.

Configurations.

A configuration is a bi-infinite sequence of letters x ∈ A Z . The set A Z of configurations is the phase space. The definition of factor can be naturally extended to configurations: for x ∈ A Z and i ≤ j, x [i,j] = x i . . . x j ⊏ x. If u ∈ A * , then u ω is the infinite word of A N consisting in periodic repetitions of u and ω u ω is the configuration of A Z consisting in periodic repetitions of u.

Topology. We endow the phase space with the Cantor topology. For j, k ∈ N and a finite set W of words of length j, we note

[W ] k the set x ∈ A Z x [k,k+j-1] ∈ W . Such a set is called a cylinder. We note [W ] C
k the complement of the cylinder [W ] k . Cylinders form a base of open sets for Cantor topology. Cellular automata. A (one-dimensional two-sided) cellular automaton (CA for short) is a parallel synchronous computation model consisting in cells distributed over the regular lattice Z. Each cell i ∈ Z of the configuration x ∈ A Z has a state x i in the finite alphabet A, which evolves depending on the state of their neighbors:

F (x) i = f (x [i-m,i-m+d-1]
)), where f : A d → A is the local rule, m ∈ Z the anchor and d ∈ N * the diameter of the CA. By abuse of notation, we use the cellular automaton as its global function F : A Z → A Z . The orbit of initial configuration x ∈ A Z is the sequence of the configurations (F j (x)) j∈N . Usually they are graphically represented by a two-dimensional space-time diagram, like in Figure 1.

The shift σ : A Z → A Z is a particular CA defined by σ(x) i = x i+1 for every x ∈ A Z and i ∈ Z which shifts configurations to the left. If the alphabet contains a special letter 0, the null CA null : A Z → A Z is another particular CA defined by null(x) i = 0. Its image set is { ω 0 ω }.

Any local rule f of a CA can be extended naturally to an application on words

f (w) = (f (w [i,i+d-1] )) 0≤i≤|w|-d , for all w ∈ A * A d .
Finally, if a CA has anchor 0, it is called an one-way cellular automata (OCA for short), since the new state of a cell only depends on its right neighbors. Hence information can only flow from right to left.

Subshifts. The one-sided shift (or simply shift when no confusion is possible), also noted σ by abuse of notation is the self-map of A N such that σ(z

) i = z i+1 , for every z ∈ A N and i ∈ N. A one-sided subshift Σ ⊂ A N is a σ-stable closed set of infinite words. The language of Σ is L(Σ) = { w ∈ A * | ∃z ∈ Σ, w ⊏ z}. It characterizes Σ since Σ = z ∈ A N ∀w ⊏ z, w ∈ L(Σ) .
A subshift Σ is nilpotent if there is some k ∈ N such that σ k (Σ) = {0 ω }. Equivalently, Σ ⊂ A k 0 ω for some k. In particular, it is finite.

Trace

Trace. In this section we define the main notion introduced in the paper, namely the trace of a CA. Definition 1 (Trace). Given a CA F , the trace of F with initial condition

x ∈ A Z is T F (x) = (F j (x) 0 ) j∈N .
In other words, it is the central column of the space-time diagram of initial configuration x (see Figure 1). The trace subshift of

F is τ (F ) = T F (A Z ). Similarly, we define T k F (x) = (F j (x) [0,k-1] ) j∈N which is the sequence of the words at positions in [0, k -1] in the space-time diagram of initial configuration x.
For instance, the trace subshift of the shift is (0 + 1) ω , it is 0 ω + 1 ω for the identity and (0 + 1)0 ω for the null CA (see [START_REF] Cervelle | Sofic trace of a cellular automaton[END_REF] for more examples).

Note that T F F = σT F and, as T F is continuous, it is a factorization between the CA and the one-sided full shift which means that their two dynamics are very closely related. For more about factorization, see [START_REF] Kůrka | Topological and symbolic dynamics[END_REF].

Subtrace. If Σ is a subshift on an alphabet B ⊂ A k , and i ∈ [0, k -1], then for all z = ((z j ) 0 . . . (z j ) k-1 ) j∈N ∈ Σ, we define its i th projection as π i (z) = ((z j ) i ) j∈N ∈ A N , and π [n,m] (z) = ((z j ) n , . . . , (z j ) m ) j∈N . We also note π(Σ) = 0≤i<k π i (Σ), which is a subshift on A.

Definition 2. Given a CA F on the alphabet B ⊂ A k , the subtrace subshift is defined by

• τ (F ) = 0≤i<k ((F j (x) 0 ) i ) j∈N x ∈ B Z = π(τ (F )).
4 The nilpotency problem

Definition 3. Consider a CA F of local rule f : A d → A and q ∈ A. A state q ∈ A is spreading if for all word u ∈ A d containing letter q, we have f (u) = q. A CA on alphabet A is q-nilpotent (or simply nilpotent) if there is some integer j for which ∀x ∈ A Z , F j (x) = ω q ω .
Note that a CA is nilpotent if and only if its trace is nilpotent.

Theorem 1 (Kari [START_REF] Kari | The nilpotency problem of one-dimensional cellular automata[END_REF]). The problem Instance: a CA F with a spreading state q Question: is F q-nilpotent? is undecidable.

Note that it is still undecidable if we restrict to OCA since two CA with the same diameter and same local rule are either both nilpotent or both non nilpotent whatever are their anchor. If the first CA F has anchor m and the second CA F ′ has anchor m ′ and if there is a k such that for all configuration x, F k (x) = ω q ω then F ′k (x) = σ k(m-m ′ ) (F k (x)) = ω q ω . Proposition 1. An OCA with a spreading state q is q-nilpotent if and only if q appears in all its space-time diagrams.

Proof. Consider a CA F . If its diameter is 1 (each cell uses only its state for the local rule), then the equivalence is trivial since for all letter a, the spacetime diagram for ω a ω contains a q after k a steps and hence for all configuration x, F max a∈A ka (x) = ω q ω . Otherwise, for every configuration x ∈ A N , there are some integers i and j such that F j (x) i = q. Note that, by spreadingness,

F j+⌈ i d ⌉ (x) 0 = q. Hence j∈N F -j ([q]) is a covering by open subsets of the compact A N , so we can find some k ∈ N such that A N = j≤k F -j ([q]) = F -k ([q]). By shift- invariance, F k (A N ) = { ω q ω }. ⊓ ⊔ Proposition 2.
Let F a CA on alphabet A, of diameter d, and with a spreading state q ∈ A. We can build a CA F ′ on alphabet {0, 1} k for some k ∈ N * , such that F ′ is (0, . . . , 0)-nilpotent if and only if F is q-nilpotent.

Proof. Let k = ⌈log 2 |A|⌉ and φ : A → {0, 1} k an injection such that φ(q) = (0, . . . , 0). F ′ can be defined by the same diameter and anchor as F , and local rule:

f ′ : ({0, 1} k ) d → {0, 1} k u → φ(f (a)) if u = φ(a) (0, . . . , 0) otherwise . ⊓ ⊔

Subtrace problems

A subtrace is somewhat the trace of a "CA" which does not apply the same evolution rule on each cell. We will first prove, by reduction from the nilpotency problem, the undecidability of a certain class of properties over subtrace subshifts, that is, non-trivial nilpotent-stable properties. In the next section, we will reduce properties over trace subshifts.

The full subtrace problem.

This section is devoted to reducing the nilpotency problem to the problem Full:

Instance: an OCA on alphabet A k+1 Question: is its subtrace equal to the full shift A N ?

Our method presents similarities with [START_REF] Ollinger | The intrinsic universality problem of one-dimensional cellular automata[END_REF].

Let F a OCA on A of local rule f , diameter d, and with a spreading state q ∈ A. From Proposition 2, we can assume without loss of generality that A = {0, 1} k for some k ∈ N * , and q = (0, . . . , 0). We can build the OCA σ ⊚ F on alphabet {0, 1} 1+k with the local rule:

g : ({0, 1} × {0, 1} k ) d → {0, 1} × {0, 1} k (((a 0 , x 0 ) . . . (a d-1 , x d-1 ))) → (a 1 , f (x 0 . . . x d-1 )) if x 0 = q (0, q) otherwise
This rule works almost like the Cartesian product of the shift on {0, 1} and F except that it applies the shift only if the state of the cell for F is not q and else goes to 0. It behaves as if F is supplying power to the shift CA and q means "no power".

Lemma 1. If F is q-nilpotent, then • τ (σ ⊚ F ) too. Otherwise, • τ (σ ⊚ F ) = A N .
Proof. We can see that the last k projections exactly represent the application of the CA F . In particular, if F is q-nilpotent, then there is some j ∈ N for which ∀x ∈ A Z , π [1,k] (T σ⊚F (x)) [j,+∞) = q ω , and from the rule we get π 0 (T σ⊚F (x) ) [j+1,+∞) = 0 ω , so

• τ (σ ⊚ F ) is (0, q)-nilpotent. On the other hand, if F is not q-nilpotent, then from Proposition 1, one can find a configuration x ∈ A Z such that ∀j ∈ N, ∀i ∈ Z, F j (x) i = q. For every z ∈ A N , define y ∈ ({0, 1} 1+k ) Z such that π [1,k] (y) = x and π 0 (y) [0,+∞) = z. The second case of the rule will never be applied in the orbit of y; hence π 0 (T σ⊚F (y) ) = z.

⊓ ⊔ Theorem 2. Problem Full is undecidable.

Proof. σ⊚F is clearly computable from F , so if we could decide whether

• τ (σ⊚F ) is A N , then from Lemma 1, we could decide whether F is nilpotent. ⊓ ⊔

Other problems.

In this section, we use the previously-built CA in order to reduce the nilpotency problem to a large class of problems over the subtrace of a CA on {0, 1} 2+k . Definition 4. A property P on subshifts is nilpotent-stable if for every subshift Σ and every nilpotent subshift H, Σ ∈ P ⇔ Σ ∪ H ∈ P .

By non-trivial property, we mean that some OCA traces respect it and some do not.

Theorem 3. For any non-trivial nilpotent-stable property P , the problem Instance: a CA F on alphabet {0, 1} k , with k ∈ N * Question: has the subtrace subshift

• τ (F ) property P ? is undecidable.

Proof. Let P be a non-trivial nilpotent-stable property of the subshifts of A N . Should we take its complementary, we can assume P is false for the full shift A N . Let H be an OCA on {0, 1} such that τ (H) ∈ P , h its local rule and d its diameter. Let F be an OCA on A k of local rule f , diameter d and with spreading state q. Without loss of generality, A = {0, 1} and q = (0, . . . , 0). We can build the OCA G = (σ ⊚ F ) × H on alphabet {0, 1} 2+k with the local rule:

g : ({0, 1} × {0, 1} k × {0, 1}) d → {0, 1} × {0, 1} k × {0, 1} ((a 0 , x 0 , b 0 ) . . . (a d-1 , x d-1 , b d-1 )) → a 1 , f (x 0 . . . x d-1 ), h(b 0 . . . b d-1 ) if x 0 = q (0, q, h(b 0 . . . b d-1 )) otherwise
The first 1+k projections are the previously built automaton σ ⊚F , and the last one represents H. Hence, • τ (G) respects P if and only if F is q-nilpotent. G is clearly computable from F , so if we could decide P , then we could decide whether F is nilpotent.

• τ (G) = • τ (σ ⊚ F ) ∪ τ (H),
⊓ ⊔

From subtrace to trace

In this section, we assume G is an OCA on A k , with A = {0, 1}, and we want to build a CA on A that simulates it in a certain way, thus transforming subtrace into trace, provided a little restriction. This construction is similar to that done in [START_REF] Cervelle | Sofic trace of a cellular automaton[END_REF]. Remark that it is well known that G can be simulated by a CA F on A, as soon as its diameter is wide enough. Each cell can see its neighborhood as words of A k and evolve accordingly. The problem is that all cells must have the same local rule, so they have to find from the neighborhood which "column" of the A k simulation they are representing. This can be achieved by delimiting meaningful words with a border word 10 k . That simulation allows to "see" the evolution of G as an evolution of F . We want a little more: all evolutions of F must not be far from an evolution of F , especially those that do not correspond to alternating meaningful words and borders words.

We have two execution modes: a simulation mode will simulate properly the execution of the OCA G on alphabet A k , and a default mode will be applied if the neighborhood contains invalid information. All modes must have an evolution that locally "looks like" some evolution of G, and in particular we have to ensure that when a mode is applied to a cell, the same mode keeps being applied there in the following generations, because a change of mode would produce an invalid trace.

Macrocells.

A concatenation of a word of A k and of the border word 10 k will be called a macrocell. Let B = A k 10 k ⊂ A h the set of macrocells, where h = 2k + 1. By construction, it has the interesting property that it cannot overlap itself on more that half of its length.

Property 1. If 0 < i ≤ k, then the intersection BA i ∩ A i B is empty (equiva- lently [B] ∩ [B] i = ∅).
Simulation mode. We will assume in the rest of the section that G has a diameter 2 (this can be easily generalized), and local rule g.

The simulation mode will be applied to macrocells that are not overlapped by another macrocell on their right. For this purpose, they have to "look" on their right (in the local rule). Let Θ = BA h \ 0<i<h A i BA h-i the set of macrocells followed by something that in no way could be understood as an overlapping macrocell. The first thing to notice is that this set is not empty, since it contains successions of two macrocells thanks to Property 1.

Lemma 2. BB ⊂ Θ. Proof. If 0 < i ≤ k, then BB ∩ A i BA h-i ⊂ (BA i ∩ A i B)A h-i = ∅. If k < i < h, then BB ∩ A i BA h-i ⊂ A i (A h-i B ∩ BA h-i ) = ∅. ⊓ ⊔
We can now define a rule on the set Θ that represents the evolution of such a macrocell that sees on its right either a macrocell abut, or at least no overlapping macrocell:

∆ : ΘA h → B u → g(u [0,k-1] , u [h,h+k-1] )10 k if u ∈ BΘ g(u [0,k-1] , u [0,k-1] )10 m otherwise .
Default mode. In the case where the neighborhood is not understandable as a valid word, we have to apply a default rule: the null CA, which has the interesting property that it erases the border words that could potentially be in an invalid place.

Combining simulation mode and default mode, we are now able to turn the function ∆ into a local rule on {0, 1}. Indeed, we can define, for anchor m = h-1 and diameter d = 4h -1:

f : {0, 1} d → {0, 1} w → ∆(u) i if w ∈ A m-i uA i , for some u ∈ ΘA h , i ∈ [0, h -1] 0 otherwise
, since such an integer i and such a word u would be unique (from the construction of Θ). This local rule is such that f (A m uA m ) = ∆(u) for every u ∈ ΘA h , which is what we wanted: it can simulate in one step the behavior of our CA G. Let F the corresponding rule. You can also note that

F ([Θ]) = [∆(ΘA h )] ⊂ [B]
by definition, and that F -1 ([1]) ⊂ 0≤j≤m [Θ] -j since the default mode only produces zeros.

Stability. The following lemmas guarantee that no cell changes its evolution mode.

Lemma 3. F -1 ([B]) = [Θ]. Proof. By construction, F -1 ([B]) ⊂ F -1 ([1] m ) ⊂ 0≤j≤m [Θ] -j . Now let x ∈ F -1 ([B]). Then, for some j ∈ [0, m], F (x) ∈ [B] ∩ F ([Θ] -j ) ⊂ [B] ∩ [B] -j .
([Θ]) ⊂ 0<i<h [B] C i . Hence, F ([Θ]) ⊂ F ([B]) \ 0<i<h [B] i = [Θ]. ⊓ ⊔
Trace. The fact the evolution modes are stable helps us conclude the simulation result.

Lemma 5. If y ∈ (A m ) N and x ∈ A N such that ∀i ∈ N, x [ih,ih+m-1] = y i ∈ A m and x [ih+m,(i+1)h-1] = 10 m , then T m F (x) = T G (y). Proof.
We can prove by induction on the generation j ∈ N, that for any i ∈ N, F j (x) [ih,(i+1)h-1] = G j (y) i 10 m . This property holds for j = 0. Now suppose it is true at generation j ∈ N, and let us prove it for generation j + 1. Let i ∈ N. F j (x) ∈ [BB] ih ⊂ Θ from the induction hypothesis and Lemma 2. Therefore, we are in execution mode between cells ih and (i + 1)h:

F j+1 (x) [ih,(i+1)h-1] = ∆(F j (x) [ih,(i+1)h-1] , F j (x) [(i+1)h,(i+2)h-1] ) = ∆(F j (y) i , F j (y) i+1 ) = F j+1 (y) i . In particular, T m F (x) = (F j (y) [0,m-1] ) j∈N = T G (y). ⊓ ⊔ Lemma 6. If p ∈ N and x ∈ A N are such that ∀i < p, x [ih,(i+2)h-1] ∈ Θ and x [ph,(p+2)h-1] / ∈ Θ; let y ∈ (A m ) N the ultimately uniform infinite word such that ∀i < p, y i = x [ih,ih+m-1] and ∀i ≥ p, y i = x [(p-1)h,(p-1)h+m-1] . Then T m F (x) = T G (y).
Proof. Similarly to the proof of Lemma 5, it can easily be proved by induction on the generation j ∈ N that for any i < p, F j (x) [ih,(i+1)h-1] = G j (y) i 10 m , since execution is always applied. Hence,

T m F (x) = T G (y). ⊓ ⊔ Lemma 7. The trace of F is • τ (G) ∪ Σ, where Σ ⊂ {0 ω , 10 ω , 1 ω }. Proof. Let x ∈ A Z .
-If x ∈ [Θ] -q for some q ∈ [0, m -1], and ∀i ∈ N, x [ih,(i+2)h-1] ∈ Θ, and, from Lemma 5, T F (x) = π i (T G (y)), where

y i = x [ih,ih+m-1] . -If x ∈ [Θ] -q for some q ∈ [0, m -1],
and there is some integer p such that ∀i

< p, x [ih,(i+2)h-1] ∈ Θ and x [ph,(p+2)h-1] / ∈ Θ, then from Lemma 6, T F (x) = π i (T G (y)), for some y ∈ (A m ) N . -If x ∈ [Θ] -q for some q ∈ [m, h -1], then by induction and Lemma 4, we can see that ∀j ∈ N, F j (x) ∈ [Θ] -q . Thus, ∀j ∈ N, F j (x) 0 = 1 if q = m and 0 if m < q < h. -Lastly, if x / ∈ [Θ] -q for any q ∈ [0, h -1]
, then default mode is applied, and, according to Lemma 3, will always be: ∀j > 0, F j (x) 0 = 0.

Putting things together, the first two cases give π(τ (G)) and the last two give {0 ω , 10 ω , 1 ω }.

⊓ ⊔

We are thereby able to "simulate" a OCA G on alphabet A m by a CA F on alphabet A. This simulation transforms the subtrace of G into the trace of F , provided a little restriction -adding three obviously nilpotent infinite words. Theorem 4. For any non-trivial nilpotent-stable property P , the problem Instance: a CA on alphabet {0, 1} Question: has its trace subshift property P is undecidable.

Proof. Let P a non-trivial nilpotent-stable property. From any OCA G on alphabet {0, 1} m , we can, using previous construction, computably build a CA F on alphabet {0, 1} such that τ (F ) =

• τ (G) ∪ Σ, where Σ = {0 ω , 10 ω , 1 ω } are nilpotent subshifts. In particular, we can notice that • τ (G) respects P if and only if τ (F ) does. So if we could decide, from the entry F , whether τ (F ) respects P , then we could decide from the entry G whether • τ (G) does.

⊓ ⊔

We have proved the undecidability of a class of problems over CA traces, which could lead us towards a Rice-like Theorem. This class is very comprehensive: fullness, finiteness, ultimate periodicity, soficness, finite type, inclusion of a particular word as a factor. . . are all nilpotent-stable non-trivial properties. On the other hand, note that context-sensitivity of the language is trivial since true for all trace subshifts according to [START_REF] Gilman | Notes on cellular automata[END_REF].

The perspectives now would be to decrease the amount of problems that are not concerned. Finite properties (which depend only on the k th prefix of the subshift, for some k ∈ N) are clearly decidable. Are they the only ones?

Our result can be easily adpated to traces of any fixed width of a CA on any given alphabet, but with arbitrarily wide neighborhoods. Another open problem would be to widen our result to study properties of the canonical factor (of width d), or at least with fixed diameter (and arbitrary alphabet). That would, in particular, comprehend the undecidability of the language classification, proved in [START_REF] Di Lena | Decidable and Computational properties of Cellular Automata[END_REF]. Nonetheless, our construction can hardly be generalized for that matter, since it is based on increasing the diameter to put more information.

2 Fig. 1 .

 21 Fig. 1. The trace seen on the space-time diagram.

  and we can use Lemma 1. If F is nilpotent, then • τ (σ ⊚ F ) too, and • τ (G) respects P since τ (H) does, and P is nilpotent-stable. Otherwise, • τ (σ ⊚ F ) = A N does not respect P . Hence,

By Property 1 ,

 1 we conclude that j = 0, i.e. F -1 ([B]) ⊂ [Θ]. Conversely, we have already seen that [Θ] ⊂ F -1 ([B]). ⊓ ⊔ Lemma 4. F ([Θ]) ⊂ [Θ]. Proof. By definition of [Θ], it is included in 0<i<h [Θ] C i . Moreover, F ([Θ] C ) ⊂ [B] C by Lemma 3. Combining the two, we get F

⋆ This work has been supported by the Interlink/MIUR project "Cellular Automata:

Topological Properties, Chaos and Associated Formal Languages", by the ANR Blanc "Projet Sycomore".


Alberto Dennunzio
email: dennunzio@disco.unimib.it

Pierre Guillon
email: pierre.guillon@univ-mlv.fr

Benoît Masson
email: benoit.masson@lif.univ-mrs.fr

Stable Dynamics of Sand Automata

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Self-organized criticality (SOC [START_REF] Bak | Self-organized criticality[END_REF]) is a common phenomenon observed in a huge variety of processes in physics, biology and computer science. A SOC system evolves to a "critical state" after some finite transient. Examples of SOC systems are: sandpiles, snow avalanches, star clusters in the outer space, earthquakes, forest fires, load balance in operating systems [START_REF] Bak | How Nature Works -The Science of SOC[END_REF]. Among them, sandpile models are a paradigmatic formal model for SOC systems [START_REF] Goles | Games on line graphs and sandpile automata[END_REF].

In [START_REF] Cervelle | On sand automata[END_REF], the authors introduced sand automata as a generalization of sandpile models and transposed them in the setting of discrete dynamical systems. A key-point of [START_REF] Cervelle | On sand automata[END_REF] was to introduce a (locally compact) metric topology to study the dynamical behavior of sand automata. A first and important result was a fundamental representation theorem similar to the well-known theorem of Hedlund for cellular automata [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF][START_REF] Cervelle | On sand automata[END_REF]. In [START_REF] Cervelle | Basic properties for sand automata[END_REF][START_REF] Cervelle | From sandpiles to sand automata[END_REF], the authors investigate sand automata by dealing with some basic set properties and decidability issues. Then, in [START_REF] Dennunzio | Topological properties of sand automata as cellular automata[END_REF], a new compact topology is introduced, inspired by the strong relation between sand automata and cellular automata. It is proved that with this new topology, the representation theorem still holds, while the compactness provides new opportunities for further topological studies of the model.

In this paper we continue the study of sand automata dynamics of [START_REF] Cervelle | Basic properties for sand automata[END_REF][START_REF] Cervelle | From sandpiles to sand automata[END_REF], using the topological framework from [START_REF] Dennunzio | Topological properties of sand automata as cellular automata[END_REF]. More precisely, we study different types of stability. Indeed, stability over time is a major issue for isolating the realistic sandpile models satisfying the SOC principles. First, we deal with the dynamical stability, i.e., the equicontinuity and ultimate periodicity properties. We prove that they are equivalent. Then, the insignificance of expansivity, a form of strong instability, suggests that the topological classification for cellular automata from [START_REF] Kůrka | Languages, equicontinuity and attractors in cellular automata[END_REF] cannot be easily generalized to sand automata.

Finally, we study nilpotency, a very strong form of dynamical stability. The classical definition of nilpotency for cellular automata [START_REF] Čulik | On the limit sets of cellular automata[END_REF][START_REF] Kari | The nilpotency problem of one-dimensional cellular automata[END_REF] is no more meaningful here, since it would prevent any sand automaton from being nilpotent. Therefore, we introduce a new definition which captures the intuitive idea that a nilpotent automaton destroys all configurations: a sand automaton is nilpotent if all configurations get closer and closer to a uniform configuration, not necessarily reaching it. Finally, we prove that this behavior is undecidable, using the undecidability of the nilpotency of spreading cellular automata.

The paper is structured as follows. In Section 2, we recall basic definitions and results on cellular automata and sand automata. Then, in Section 3, results on the topological stability of sand automata are proved and discussed. Nilpotency of sand automata is then defined and proved undecidable in Section 4.

Definitions

Cellular Automata

Let A be a finite alphabet. A CA configuration of dimension d is a function from Z d to A. The set A Z d of all the CA configurations is called the CA configuration space. This space is usually equipped with the Tychonoff metric d T defined by

∀x, y ∈ A Z d , d T (x, y) = 2 -k where k = min |j| : j ∈ Z d , x j = y j .
The topology induced by d T coincides with the product topology induced by the discrete topology on A. It makes the CA configuration space is a Cantor space: it is compact, perfect (i.e., it has no isolated points) and totally disconnected.

A cellular automaton (CA) is a quadruple A, d, r, g , where A is the alphabet, also called the state set, d ∈ N is the dimension, r ∈ N is the radius and g : M d r → A is the local rule of the automaton. The local rule g induces a global rule G :

A Z d → A Z d defined as follows, ∀x ∈ A Z d , ∀i ∈ Z d , G(x) i = g M i r (x) ,
where M i r (x) ∈ M d r is the finite portion of x of reference position i ∈ Z d and radius r defined by ∀k ∈

[-r, r] d , M i r (x) k = x i+k . For any k ∈ Z d the shift map σ k : A Z d → A Z d is defined by ∀x ∈ A Z d , ∀i ∈ Z d , σ k (x) i = x i+k . A function F : A Z d → A Z d is said to be shift-commuting if ∀k ∈ Z d , F • σ k = σ k • F .
Note that CA are exactly the class of all shiftcommuting functions which are (uniformly) continuous with respect to the Tychonoff metric (Hedlund's theorem from [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF]). For the sake of simplicity, we will make no distinction between a CA and its global rule G.

For a given CA, a state s ∈ A is quiescent (resp., spreading) if for all matrices U ∈ M d r such that ∀k ∈ [-r, r] d , (resp., ∃k ∈ [-r, r] d ) U k = s, it holds that g(U ) = s. Remark that a spreading state is also quiescent. A CA is said to be spreading if it has a spreading state. In the sequel, the spreading state of any spreading CA will be denoted 0 ∈ A.

SA Configurations

A configuration is a set of sand grains organized in piles and distributed all over the d-dimensional lattice Z d . A pile is an element of Z = Z ∪ {-∞, +∞} which represents a number of grains. One pile is positioned in each point of the lattice Z d . Formally, a configuration x is a function from Z d to Z which associates any vector i = (i 1 , . . . , i d ) ∈ Z d with the number x i ∈ Z of grains in the pile of position i. When the dimension d id known without ambiguity, we note 0 the null vector of Z d . Denote by C = Z Z d the set of all configurations.

A configuration x ∈ C is said to be constant if there is an integer c ∈ Z such that for any vector i ∈ Z d , x i = c. In that case we write x = c. A configuration x ∈ C is said to be bounded if there exist two integers m 1 , m 2 ∈ Z such that for all vectors i ∈ Z d , m 1 ≤ x i ≤ m 2 . Denote by B the set of all bounded configurations.

A measuring device β m r of precision r ∈ N and reference height m ∈ Z is a function from Z to [-r, r] defined as follows

∀n ∈ Z, β m r (n) =    +∞ if n > m + r , -∞ if n < m -r , n -m otherwise.
A measuring device is used to evaluate the relative height of two piles, with a bounded precision. This is the technical basis of the definition of cylinders, distance and ranges which are used all along this article.

In [START_REF] Dennunzio | Topological properties of sand automata as cellular automata[END_REF], a topology, inspired by the topology on CA configurations, is defined as follows.

Definition 1 (cylinder). For any configuration x ∈ C, for any r ∈ N, and for any i ∈ Z d , the cylinder of x centered on i and of radius r is the d-dimensional matrix C i r (x) ∈ M d r defined on the finite alphabet [-r, r] by

∀k ∈ [-r, r] d , C i r (x) k = β 0 r (x i+k ) . Definition 2.
For any pair of configurations x, y ∈ C, we define d(x, y) = 2 -k where k = min r ∈ N : C 0 r (x) = C 0 r (y) . As a consequence, two configurations x, y are compared by putting boxes (the cylinders) at height 0 around the corresponding piles indexed by 0. The integer k is the size of the smallest cylinders in which a difference appears between x and y.

That topology makes the SA configuration space perfect, totally disconnected, and, unlike the original topology used in [START_REF] Hedlund | Endomorphisms and automorphisms of the shift dynamical system[END_REF][START_REF] Cervelle | On sand automata[END_REF], compact (see [START_REF] Dennunzio | Topological properties of sand automata as cellular automata[END_REF]).

Sand Automata

For any integer r ∈ N, for any configuration x ∈ C and any index i ∈ Z d with x i = ±∞, the range of center i and radius r is the

d-dimensional matrix R i r (x) ∈ M d r on the finite alphabet A = [-r, r] ∪ ⊥ such that ∀k ∈ [-r, r] d , R i r (x) k = ⊥ if k = 0 , β xi r (x i+k )
otherwise. The range is used to define a sand automaton. It is a kind of cylinder, where the observer is always located on the top of the pile x i (called the reference).

It represents what the automaton is able to see at position i. Sometimes the central ⊥ symbol may be omitted for simplicity sake. The set of all possible ranges of radius r, in dimension d, is denoted by R d r . A sand automaton (SA) is a deterministic finite automaton working on configurations. Each pile is updated synchronously, according to a local rule which computes the variation of the pile by means of the range. Formally, a SA is a triple d, r, f , where d is the dimension, r is the radius and f : R d r → [-r, r] is the local rule of the automaton. The global rule F : C → C is defined by

∀x ∈ C, ∀i ∈ Z d , F (x) i = x i if x i = ±∞ , x i + f (R i r (x)) otherwise.
The following example illustrates a sand automaton whose behavior will be studied in Section 4. For more examples, we refer to [START_REF] Cervelle | From sandpiles to sand automata[END_REF].

Example 1 (the automaton N ). This automaton destroys a configuration by collapsing all piles towards the lowest one. It decreases a pile when there is a lower pile in the neighborhood. When no misunderstanding is possible, we identify a SA with its global rule F . For any k ∈ Z d , we extend the definition of the shift map to C,

Let N = 1, 1, f N of global rule F N where ∀a, b ∈ [-1, 1], f N (a, b) = -1 if a < 0 or b < 0 , 0 otherwise.
σ k : C → C is defined by ∀x ∈ C, ∀i ∈ Z d , σ k (x) i = x i+k . The raising map ρ : C → C is defined by ∀x ∈ C, ∀i ∈ Z d , ρ(x) i = x i + 1. A function F : C → C is said to be vertical-commuting if F • ρ = ρ • F . A function F : C → C is infinity-preserving if for any configuration x ∈ C and any vector i ∈ Z d , F (x) i = +∞ if and only if x i = +∞ and F (x) i = -∞ if and only if x i = -∞.
With the topology from [START_REF] Dennunzio | Topological properties of sand automata as cellular automata[END_REF], the Hedlund-like representation theorem for SA from [START_REF] Cervelle | On sand automata[END_REF] remains valid.

Theorem 1 ([8]

). A mapping F : C → C is a SA if and only if F is (uniformly) continuous, shift-commuting, vertical-commuting and infinity-preserving.

Some Dynamical Behaviors

The concepts that first come to mind to formalize the notion of stability are inspired by the topological classifications given in [START_REF] Robert | Classes of linear automata[END_REF][START_REF] Kůrka | Languages, equicontinuity and attractors in cellular automata[END_REF] for CA. In [START_REF] Kůrka | Languages, equicontinuity and attractors in cellular automata[END_REF], CA are classified into four classes, from the most stable to the most unstable behavior: equicontinuous CA, non-equicontinuous CA admitting an equicontinuity configuration, sensitive but not positively expansive CA, positively expansive CA. In this section we consider these classes from the SA point of view, and we introduce the notion of ultimate periodicity, useful for the characterization of SOC systems. We prove that there exist no positively expansive SA and characterize equicontinuous SA as the ultimately periodic SA.

First, recall basic definitions. Let (X, m) a metric space and let H : X → X be a continuous application. An element x ∈ X is an equicontinuity point for H if for any ε > 0, there exists δ > 0 such that for all y ∈ X, m(x, y) < δ implies that ∀n ∈ N, m(H n (x), H n (y)) < ε. The map H is equicontinuous if for any ε > 0, there exists δ > 0 such that for all x, y ∈ X, m(x, y) < δ implies that ∀n ∈ N, m(H n (x), H n (y)) < ε. An element x ∈ X is ultimately periodic for H if there exist two integers n ≥ 0 (the preperiod) and p > 0 (the period) such that H n+p (x) = H n (x). H is ultimately periodic if there exist n ≥ 0 and p > 0 such that H n+p = H n . If X is compact, H is equicontinuous (resp. ultimately periodic) iff all elements of X are equicontinuity points (resp. ultimately periodic). H is sensitive (to the initial conditions) if there is a constant ε > 0 such that for all points x ∈ X and all δ > 0, there is a point y ∈ X and an integer n ∈ N such that m(x, y) < δ but m(F n (x), F n (y)) > ε. H is positively expansive if there is a constant ε > 0 such that for all distinct points x, y ∈ X, there exists n ∈ N such that m(H n (x), H n (y)) > ε.

One-dimensional SA are very interesting models, which complexity lies somewhere between one-dimensional and two-dimensional CA. Indeed we have seen in the previous section that the latter can simulate SA, and it was shown in [START_REF] Cervelle | From sandpiles to sand automata[END_REF] that SA could simulate the former. A classification of one-dimensional cellular automata in terms of their dynamical behavior was given in [START_REF] Kůrka | Languages, equicontinuity and attractors in cellular automata[END_REF]. Things are very different as soon as we get into the second dimension, as noted in [START_REF] Shereshevsky | Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms[END_REF][START_REF] Sablik | Topological dynamics of 2D cellular automata[END_REF]. The question is now whether the complexity of the SA model is closer to that of the lower or the higher-dimensional CA.

The classification from [START_REF] Kůrka | Languages, equicontinuity and attractors in cellular automata[END_REF] is no more relevant in the context of SA since the class of positively expansive SA is empty. This result can be related to the absence of positively expansive two-dimensional CA (see [START_REF] Shereshevsky | Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms[END_REF]), though the proof is much different. Proposition 1. There are no positively expansive SA.

Proof. Let F a SA and δ = 2 -k > 0. Take two distinct configurations x, y ∈ C such that ∀i ∈ [-k, k], x i = y i = +∞. By infinity-preservingness, we get ∀n ∈ N, ∀i ∈ [-k, k], F n (x) i = F n (y) i = +∞, hence d(F n (x), F n (y)) < δ. ⊓ ⊔
In a similar way as Theorem 4 of [START_REF] Kůrka | Languages, equicontinuity and attractors in cellular automata[END_REF], the two different notions of stability, equicontinuity and ultimate periodicity, are proved to be equivalent. The proof uses the following lemma, which allows a better understanding of equicontinuity for SA. Lemma 1. If F is an equicontinuous SA, then the variation of a pile is bounded by the differences in an initial neighborhood, i.e., there is some integer l such that all configurations x ∈ C with x 0 = 0 satisfy

∀n ∈ N, |F n (x) 0 | ≤ max |i|≤l |xi|<∞ |x i | .
Proof. If F is equicontinuous, in particular, for ε = 2 0 , there exists δ = 2 -l such that for all x, y ∈ C, if

C 0 l (x) = C 0 l (y), then ∀n ∈ N, C 0 0 (F n (x)) = C 0 0 (F n (y)). First, consider a configuration y that has infinite l-neighborhood, i.e., ∀i ∈ [-l, l] , y i / ∈ [-l, l]. Let z defined by z i = +∞ if y i ≥ 0 and z i = -∞ if y i < 0, in such way that C 0 l (y) = C 0 l (z). Then ∀n ∈ N, C 0 0 (F n (y)) = C 0 0 (F n (z)) = C 0 0 (z), i.e., F n (y) 0 < -l ⇔ y 0 < -l and F n (y) 0 > l ⇔ y 0 > l.
Now, let x a configuration such that x 0 = 0 and m = max |i|≤l |xi|<∞

|x i |. Notice that ρ l+m+1 (x) has infinite l-neighborhood, since x i ≤ m or x i = +∞ for |i| ≤ l. Hence, as seen before, ∀n ∈ N, F n (x) 0 ≤ m. A symmetrical reasoning on ρ -l-m-1 (x) gives ∀n ∈ N, |F n (x) 0 | ≤ m. ⊓ ⊔ Proposition 2.
If F is a SA, then the following statements are equivalent:

1. F is equicontinuous. 2. F is ultimately periodic.

Proof. 2⇒1: Let F be such that with F n+p = F n for some n ≥ 0, p > 0. Since F, F 2 , . . . , F n+p-1 are uniformly continuous maps, for any ε > 0 there exists δ > 0 such that for all x, y ∈ C with d(x, y) < δ, it holds that ∀q ∈ N, q < n + p, d(F q (x), F q (y)) < ε. Since for any t ∈ N, F t is equal to some F q with q < n + p, the map F is equicontinuous. 1⇒2: Let F an equicontinuous SA and l, as in Lemma 1, such that for all

x, y ∈ C, if C 0 l (x) = C 0 l (y), then ∀n ∈ N, C 0 0 (F n (x)) = C 0 0 (F n (y))
. Let x a configuration such that x 0 is finite. Should we vertically shift it, we can assume that x 0 = 0. Let y the configuration defined by y i = max(min(x i , l + 1), -l -1) if -l ≤ i ≤ l and y i = +∞ otherwise, in such way that

C 0 l (x) = C 0 l (y). Lemma 1 gives ∀i ∈ [-l, l] , ∀n ∈ N, |F n (y) i | ≤ 2l + 2.
We can thus find some preperiod q y and some period p y such that ∀i ∈ [-l, l] , F py+qy (y) i = F qy (y) i . The other piles being infinite, hence invariant, we get F py+qy (y) = F qy (y). As a consequence, C 0 0 (F py+qy (x)) = C 0 0 (F qy (x)). Define p (resp., q) as the least common multiple (resp., maximum) of all p y (resp., q y ) for y a configuration such that |y i | ≤ l + 1 if |i| ≤ l and y i = +∞ otherwise. Then, for every configuration x, C 0 0 (F p+q (x)) = C 0 0 (F q (x)); in particular for vertical and horizontal shifts of x, which give F p+q (x) = F q (x). ⊓ ⊔ An important open question in the dynamical behavior of SA is the existence of non-sensitive SA without any equicontinuity configuration. An example for two-dimensional CA is given in [START_REF] Sablik | Topological dynamics of 2D cellular automata[END_REF], but their method can hardly be adapted for SA. However, we conjecture that such SA exist, which would lead to a classification of SA into four classes: equicontinuous, admitting an equicontinuity configuration (but not equicontinuous), non-sensitive without equicontinuity configurations, sensitive.

Another issue is the decidability of these classes. In [START_REF] Cervelle | Basic properties for sand automata[END_REF], the undecidability of SA ultimate periodicity was proved on the particular subsets of finite and periodic configurations. It follows directly that equicontinuity on these subsets is undecidable. The question is still open for the whole configuration space C.

Nilpotency

In this section we give a definition of nilpotency, the most stable dynamics of a dynamical system, adapted to SA. Then, we prove that this nilpotency behavior is undecidable (Theorem 3).

Nilpotency of CA

Here we recall the basic definitions and properties of nilpotent CA. Nilpotency is among the simplest dynamical behavior that an automaton may exhibit. Intuitively, a system is nilpotent if it destroys every piece of information in any initial configuration, reaching a common constant configuration after a while. For CA, this is formalized as follows.

Definition 3 (CA nilpotency [START_REF] Čulik | On the limit sets of cellular automata[END_REF][START_REF] Kari | The nilpotency problem of one-dimensional cellular automata[END_REF]).

A CA G is nilpotent if ∃c ∈ A, ∃N ∈ N ∀x ∈ A Z d , ∀n ≥ N, G n (x) = c .
Remark that, because of the compactness of the CA configuration space, a CA is nilpotent if and only if it is nilpotent for all initial configurations (i.e., all configurations eventually reach the same configuration).

Spreading CA have the following stronger characterization.

Proposition 3 ([6]

). A CA of global rule G, with spreading state 0, is nilpotent if and only if for all configurations

x ∈ A Z d , lim n→∞ d T (G n (x), 0) = 0.
This equivalence is very useful since the CA nilpotency has been proved undecidable in [START_REF] Kari | The nilpotency problem of one-dimensional cellular automata[END_REF], even for the restricted class of spreading CA.

Theorem 2 ([12]

). For a given state s, it is undecidable to know whether a cellular automaton with spreading state s is nilpotent.

Nilpotency of SA

A direct adaptation of Definition 3 to SA is vain. Indeed, assume F is a SA of radius r. For any k ∈ Z d , consider the configuration x k ∈ B defined by x k 0 = k and x k i = 0 for any i ∈ Z d \{0}. Since the pile of height k may decrease at most by r during one step of evolution of the SA, and the other piles may increase at most by r, x k requires at least ⌈k/2r⌉ steps to reach a constant configuration. Thus, there exists no common integer n such that all configurations x k reach a constant configuration in time n. This is a major difference with CA, which is essentially due to the unbounded set of states and to the infinity-preserving property.

Thus, we propose to label as nilpotent the SA which make every pile approach a constant value, but not necessarily reaching it ultimately. This nilpotency notion, inspired by Proposition 3, is formalized as follows for a SA F :

∃c ∈ Z, ∀x ∈ C, lim n→∞ d(F n (x), c) = 0 .
Remark that c shall not be taken in the full state set Z, because allowing infinite values for c would not correspond to the intuitive idea that a nilpotent SA "destroys" a configuration (otherwise, the raising map would be nilpotent). Anyway, this definition is not satisfying because of the vertical commutativity: two configurations which differ by a vertical shift reach two different configurations, and then no nilpotent SA may exist. A possible way to work around this issue is to make the limit configuration depend on the initial one:

∀x ∈ C, ∃c ∈ Z, lim n→∞ d(F n (x), c) = 0 .
Again, since SA are infinity-preserving, an infinite pile cannot be destroyed (nor, for the same reason, can an infinite pile be built from a finite one). Therefore nilpotency has to involve the configurations of Z Z d , i.e., the ones without infinite piles. Moreover, every configuration x ∈ Z Z d made of regular steps (i.e., in dimension 1, for all i ∈ Z, x ix i-1 = x i+1x i ) is invariant by the SA rule (possibly composing it with the vertical shift). So it cannot reach nor approach a constant configuration. Thus, the larger reasonable set on which nilpotency might be defined is the set of bounded configurations B. This leads to the following formal definition of nilpotency for SA.

Definition 4 (SA nilpotency).

∀x ∈ B, ∃c ∈ Z, lim n→∞ d(F n (x), c) = 0 .
The following proposition shows that the class of nilpotent SA is nonempty. Remark that similar nilpotent SA can be constructed with any radius and in any dimension.

Proposition 4. The SA N from Example 1 is nilpotent. Proof. Let x ∈ B, let i ∈ Z such that for all j ∈ Z, x j ≥ x i . Clearly, after x i+1 -x i steps, F xi+1-xi N (x) i+1 = F xi+1-xi N (x) i = x i .
By immediate induction, we obtain that for all j ∈ Z there exists

n j ∈ N such that F nj N (x) j = x i , hence lim n→∞ d(F n N (x), x i ) = 0. ⊓ ⊔

Undecidability

The main result of this section is that SA nilpotency is undecidable (Theorem 3), by reducing to it the nilpotency of spreading CA. This emphasizes the fact that the dynamical behavior of SA is very difficult to predict. We think that this result might be used as the reference undecidable problem for further questions on SA.

Problem Nil instance: a SA A = d, r, λ ; question: is A nilpotent?

Theorem 3. The problem Nil is undecidable.

Proof. This is proved by reducing Nil to the nilpotency of spreading cellular automata. Remark that it is sufficient to show the result in dimension 1. Let S be a spreading cellular automaton S = A, 1, s, g of global rule G, with finite set of integer states A ⊂ N containing the spreading state 0. We simulate S with the sand automaton A = 1, r = max(2s, max A), f of global rule F using the following technique, also developed in [START_REF] Cervelle | From sandpiles to sand automata[END_REF]. Let ξ : A Z → B be a function which inserts markers every two cells in the CA configuration to obtain a bounded SA configuration. These markers allow the local rule of the SA to know the absolute state of each pile and behave as the local rule of the CA. To simplify the proof, the markers are put at height 0 (see Figure 2):

∀y ∈ A Z , ∀i ∈ Z, ξ(y) i = 0 (marker) if i is odd , y i/2 otherwise.
This can lead to an ambiguity when all the states in the neighborhood of size 4s + 1 are at state 0, as shown in the picture. But as in this special case the state 0 is quiescent for g, this is not a problem: the state 0 is preserved, and markers are preserved. The local rule f is defined as follows, for all ranges R ∈ R 1 r ,

f (R) =    0 if R -2s+1 , R -2s+3 , . . . , R -1 , R 1 , . . . , R 2s-1 ∈ A , g(R -2s + a, R -2s+2 + a, . . . , R -2 + a, a, R 2 + a, . . . , R 2s + a) -a if R -2s+1 = R -2s+3 = • • • = R 2s-1 = a < 0 and -a ∈ A .
(1) The first case is for the markers (and state 0) which remain unchanged, the second case is the simulation of g in the even piles. As proved in [START_REF] Cervelle | From sandpiles to sand automata[END_REF], for any y ∈ A Z it holds that ξ(G(y)) = F (ξ(y)). The images by f of the remaining ranges will be defined later on, first a few new notions need to be introduced.

A sequence of consecutive piles (x i , . . . , x j ) from a configuration x ∈ B is said to be valid if it is part of an encoding of a CA configuration, i.e., x i = x i+2 = • • • = x j (these piles are markers) and for all k ∈ N such that 0 ≤ k < (ji)/2, x i+2k+1x i ∈ A (this is a valid state). We extend this definition to configurations, when i = -∞ and j = +∞, i.e., x ∈ ρ c • ξ(A Z ) for a given c ∈ Z (x ∈ B is valid if it is the raised image of a CA configuration). A sequence (or a configuration) in invalid if it is not valid.

First we show that starting from a valid configuration, the SA A is nilpotent if and only if S is nilpotent. This is due to the fact that we chose to put the markers at height 0, hence for any valid encoding of the CA x = ρ c • ξ(y), with y ∈ A Z and c ∈ Z,

lim n→∞ d T (G n (y), 0) = 0 if and only if lim n→∞ d(F n (x), c) = 0 .
It remains to prove that for any invalid configuration, A is also nilpotent. In order to have this behavior, we add to the local rule f the rules of the nilpotent automaton N for every invalid neighborhood of width 4s + 1. For all ranges R ∈ R 1 r not considered in Equation (1),

f (R) = -1 if R -r < 0 or R -r+1 < 0 or • • • or R r < 0 , 0 otherwise. (2)
Let x ∈ B be an invalid configuration. Let k ∈ Z be any index such that ∀l ∈ Z, x l ≥ x k . Let i, j ∈ Z be respectively the lowest and greatest indices such that i ≤ k ≤ j and (x i , . . . , x j ) is valid (i may equal j). Remark that for all n ∈ N, (F n (x) i , . . . , F n (x) j ) remains valid. Indeed, the markers are by construction the lowest piles and Equations ( 1) and ( 2) do not modify them. The piles coding for non-zero states can change their state by Equation ( 1), or decrease it by 1 by Equation ( 2), which in both cases is a valid encoding. Moreover, the piles x i-1 and x j+1 will reach a valid value after a finite number of steps: as long as they are invalid, they decrease by 1 until they reach a value which codes for a valid state. Hence, by induction, for any indices a, b ∈ Z, there exists N a,b such that for all n ≥ N a,b the sequence (F n (x) a , . . . , F n (x) b ) is valid.

In particular, after N -2N r-1,2N r+1 step, there is a valid sequence of length 4N r + 3 centered on the origin (here, N is the number of steps needed by S to reach the configuration 0, given by Definition 3). Hence, after N -2N r,2N r + N steps, the local rule of the CA S applied on this valid sequence leads to 3 consecutive zeros at positions -1, 0, 1. All these steps are illustrated on Figure 3.

In a similar way, we prove that for all n ≥ N -2N r-k,2N r+k +N , the sequence (F n (x) -k , . . . , F n (x) k ) is constant and does not evolve as n grows. Therefore, there exists c ∈ Z such that lim n→∞ d(F n (x), c) = 0. We just proved that A is nilpotent, i.e., lim n→∞ d(F n (x), c) = 0 for all x ∈ B, if and only if S is nilpotent (because of the equivalence of definitions given by Proposition 3), so Nil is undecidable (Theorem 2). ⊓ ⊔

Conclusion

In this article we have continued the study of sand automata, using the compact topology on the SA configuration space introduced in [START_REF] Dennunzio | Topological properties of sand automata as cellular automata[END_REF]. This topology, inspired by the topology on CA, may facilitate studies about dynamical and topological properties of SA, as for the proof of the equivalence between equicontinuity and ultimate periodicity (Proposition 2). Then, we have given a definition of nilpotency. Although it differs from the standard one for CA, it captures the intuitive idea that a nilpotent automaton "destroys" configurations. Finally, we have proved that SA nilpotency is undecidable (Theorem 3). This fact enhances the idea that the behavior of a SA is hard to predict. We also think that this result might be used as a fundamental undecidability result, which could be reduced to other SA properties.

Besides, in the context of CA, nilpotency clearly implies ultimate periodicity. It appears that with our definitions, nilpotency of SA is not necessarily a particular case of ultimate periodicity (N is not ultimately periodic). However, it would be interesting to see if it could be linked to other weaker stability notions.

Moreover, the study of global properties such as injectivity and surjectivity and their corresponding dimension-dependent decidability problems could help to understand if d-dimensional SA look more like d-dimensional or d + 1dimensional CA. Unfortunately, deciding these dynamical properties remains a major problem. Similarly, it would be interesting to solve the open question of the dichotomy between sensitive SA and those with equicontinuous configurations. A potential counter-example would give a more precise idea of the dynamical behaviors represented by SA.

For

  all a, b ∈ Z with a ≤ b, let [a, b] = {a, a + 1, . . . , b} and [a, b] = [a, b] ∪ {+∞, -∞}. Let N + be the set of positive integers. For a vector i ∈ Z d , denote by |i| the infinite norm of i. Let A a (possibly infinite) alphabet, and r, d ∈ N * . Denote by M d r the set of all the d-dimensional vectors of the hyper-rectangle [-r, r] d , with values in A.

Fig. 1 .

 1 Fig. 1. Illustration of the behavior of N .

Fig. 2 .

 2 Fig.2. Illustration of the function ξ used in the simulation of the spreading CA S by A. The thick segments are the markers used to distinguish the states of the CA, put at height 0. There is an ambiguity for the two piles indicated by the arrows: with a radius 2, the neighborhoods are the same, although one of the piles is a marker and the other the state 0.

Fig. 3 .

 3 Fig. 3. Destruction of the invalid parts. The lowest valid sequence (in gray) extends until it is large enough. Then after N other steps the 3 central piles (hatched) are destroyed because the rule of the CA is applied correctly.

⋆ This work has been supported by the Interlink/MIUR project "Cellular Automata:

Topological Properties, Chaos and Associated Formal Languages", by the ANR Blanc "Projet Sycomore" and by the PRIN/MIUR project "Formal Languages and Automata: Mathematical and Applicative Aspects".


Frédéric Fauberteau
email: fauberte@univ-paris-est.fr

Serge Midonnet
email: midonnet@univ-paris-est.fr

Dan Istrate
email: dan.istrate@esigetel.fr

Power Saving of Real Time Embedded Sensor for Medical Remote Monitoring

The power saving is one of the important issue in the embedded systems. To reduce the consumption of the microprocessor of such a system, a way is to power down it when it is inactive. Theoretically, the time during which the microprocessor is inactive represents a pure gain of energy. But practically, we must consider that this time comprises a slot of time during which the clock must be synchronized. We propose to aggregate the idle times of the microprocessor to power down it the least possible but for the longest time possible. This aggregation can be perform by using a Slack Stealer algorithm.

Introduction and Application context

The context of the present study of power saving is the medical remote monitoring for elderly. The proportion of elderly is increasing in all societies throughout the world. As they are becoming older, they want to preserve their independence, autonomy and way of life. Several research teams have developed a number of systems for inhome health care monitoring and prevention towards day life risks. These systems are based on the deployment of several sensors in home in order to prevent and/or detect critical situations. They offer the comfort and independence of staying at home, the security of daily monitoring and proper medical attention. These sensors need to communicate with a central unit which take the decision to send the emergency in a distress case. In order to install the sensors a wireless solution is the only acceptable but which imply also a good autonomy.

To provide one answer to the medical remote monitoring, we assembled a group of researches from different backgrounds within a consortium (QuoVADis1 ) in order to develop a platform for several uses and to meet the needs iden-tified above. QuoVADis is a French National project which aims to answering two of the problems arising from keeping elderly people at home: cognitive stimulation and the safety indoor.

The first platform developed within this project [START_REF] Istrate | Information extraction from sound for medical telemonitoring[END_REF] manages a system consisting of three modalities: a set of microphones disposed into the living rooms of the home of the elderly, a portable device that can measure heart rate, detect posture and possibly the fall of the person equipped and a set of infrared sensors that detect the presence of the person in a given part and also the standing posture of the person in question. The output of these three heterogeneous systems are collected, processed and fused through a multimodal platform (EMUTEM) [START_REF] Medjahed | A multimodal platform for database recording and elderly people monitoring[END_REF].

The sound environment is used like an important source of information about the possible distress situations (screams, glass breaking, dishes, distress expressions). All microphones in the current implementation are connected to a central unit (embedded PC) in order to analyze the sound environment [START_REF] Istrate | Generic implementation of a distress sound extraction system for elder care[END_REF] in real time. We Analise currently the possibility to decentralize the treatments and to allow the use of embedded system based on DSP. This study concerning the task organization aims to evaluate the cost in terms of precessing time and power consumption in the case of decentralization of sound environment analyze.

The paper is organized as follows. In Section 2, we give a model representing a theoretical view of a sensor embedded system. In Section 3, we present several kind of class of Slack Stealer algorithm and we justify our choice. In Section 4, we show results of simulation. Finally, we conclude in Section 5 and we introduce future work in Section 6.

Preliminary Definitions

Sensor Model

Because we propose a general solution instead of a particular implementation for a specific system, we must introduce a model representing a sensor embedded system. This model is made of three modules : a set of sensors, communication and processing modules.

Communication Processing Sensors

Decision

Reduction

Control

Figure 1. A model for a sensor embedded system

The sensors module corresponds to the sensor part of the sensor node. The sensor part collects data about its environment. This module generates a stream of messages which will be sent to the processing module.

The communication module enables a sensor node to communicate with other sensor nodes. Other sensor nodes collect data which can be received by this module and the suitable streams of messages are sent to the processing module. In the same way, locally processed data can be sent to other sensor nodes.

We will consider the processing module as a real-time system since it processes the streams of received messages which have time constraints. We divide this module in three functions.

• The control function is the most important one for our study. It provides controls over the system. In fact it can decide the admission of a new stream or the turning out of the processor,

• The decrease can apply operations over the stream to reduce the quantity of data. These operations can be logical : AND, OR, arithmetic : plus, average or more complex,

• The decision function can generate events according to the different dart's in the streams.

Real-Time Systems

Real-time systems are sets of tasks which have a priority, a cost and a deadline. The cost of a task is a worst case execution time. These tasks must not run over their deadline. The scheduler executes the available task with the highest priority. In our study, we consider preemptive scheduler with fixed priority. In such a scheduler, priority are not inheritable and a task can stop another task which has a lower priority. We can simply define the slack time in such a system as the period when the system is inactive.

Several kinds of task exists:

• periodic tasks which have a period. At each period, they are activated and an instance of these tasks must be executed,

• sporadic tasks which have a pseudo-period. They have the same properties that the periodic tasks but the pseudo-period is the minimum inter-arrival period. We can consider the worst pseudo-period for this type of task and it becomes easily assimilated with periodic tasks,

• aperiodic tasks which have no period. We cannot expect the arrival instant of these tasks.

In order to make our solution conceivable, we must consider aperiodic tasks as not the main type of task in the system. We can suffer aperiodic task in so much as their arrival is infrequent. Otherwise any speculation is possible.

Idle Times

A simple way to manage idle times is the scheduling of a task which has the priority the lowest. We can fix for this task an arbitrarily high cost. We just want this task to be executed when the system is inactive. This task could power down the processor. But without any scheduler modification, it can not predict its execution time. If the execution time of the sleeping task is lower than the necessary time to start the processor, some tasks can be postponed and don't meet their deadline. So we must add the time to power down and restart the processor in the worst case execution time to each periodic task. The advantage of this method is its simplicity. But we must increase the cost of the tasks because we can not know the length of the period of inactivity.

Because the over-cost of the first method is too high, we propose the use of a periodic task called "task server". We set its periodic cost called its capacity. So the time for starting the processor can be incorporated in the server cost. This method avoids to don't modify the worst case execution time of each periodic tasks. But the polling server can use not all the available idle times.

This method builds on slack stealer algorithms. These algorithms allow to compute the maximal value of slack times postponing periodic tasks with the constraint that they meet their deadline. We present these algorithms in the next section. The advantage of this method is that many scattered slack times can be aggregated. So the processor can be powered down less often but longer.

Slack Stealer Algorithms

The Slack is the maximum time that all tasks of the realtime system can be delayed without missing their deadline. We present in the following paragraphs several classes of algorithms called Slack Stealer which compute the Slack and we justify the choice of the last class, the approximate Slack Stealer algorithms.

The class of static algorithms is historically represented by the Lehoczky and Ramos-Thuel algorithm [START_REF] Thuel | Algorithms for scheduling hard aperiodic tasks in fixed-priority systems using slack stealing[END_REF]. These algorithms compute the Slack value for each instance of each task before the starting up of the system and store it. During the execution of the system, the value of the Slack is known at t instant without more computation. These algorithms seem attractive because their don't require computation when the system is on-line. But they assume that the instants of the activation of the tasks are known. This assumption is restrictive in our case. Furthermore, a non negligible space is needed to stock the Slack values. This class of algorithms is not a good choice to implement our solution.

The class of dynamic algorithms is well represented by the Davis algorithm [START_REF] Davis | Scheduling slack time in fixed priority preemptive systems[END_REF]. Contrary to static algorithms, they don't perform precomputation and so, they don't stock values in memory. These algorithms compute the available Slack in the system on demand. They also seem attractive, but the complexity of the computation is in O(n 2 ) where n is the number of tasks. Thus the implementation of such an algorithm is not possible for our solution.

The class of approximate algorithms is known to compute estimation of the Slack value. The algorithms of [START_REF] Thuel | Algorithms for scheduling hard aperiodic tasks in fixed-priority systems using slack stealing[END_REF] and [START_REF] Davis | Scheduling slack time in fixed priority preemptive systems[END_REF] give optimal values. Even if the algorithm presented in [START_REF] Masson | Slack time evaluation with rtsj[END_REF] give values which can be non maximal, it compute the Slack with linear complexity function of the number of tasks. This class of algorithms offer a good compromise between the computation time and the correctness of the result. We can implement such an algorithm for our solution. We show in Figure 2 the idea of our solution. We represented in a) a task representing the treatment of a event. This task is periodic and we power down the system when it is idle. In b), we show that the time during which the sensor is powered down can be increased by delaying the task. Slack Stealer algorithms allows us to know the length of the delay. In our example, we fix the cost of the task to 2 units of time and we fix the clock synchronization duration to 1 unit of time. During the clock synchronization, the system is restarted but it is not usable. Without the Slack management, the system can be powered down during 7 × 4 = 28 units of time. With the Slack management, the system is powered down 2 times instead of 4 and during 2 × 15 = 30 units of time.

Simulation Results

The results of simulation presented in the following section was obtained from a real-time simulator which was developed by Masson [START_REF] Masson | Real-time systems simulator (rtss)[END_REF].

Firstly, we consider the instants when the processor can be switch off. Secondly, we compare various methods to exploit idle times. We represent in Figure 3, a system of 3 periodic tasks. The task τ 1 is the most priority and τ 3 the less priority. When many tasks are active in the same time, the most priority are executed. We also represent the value of the Slack at each instant t. "Exact Slack" corresponds to the value computed from a dynamic algorithm [START_REF] Davis | Scheduling slack time in fixed priority preemptive systems[END_REF] and "Approximate Slack" corresponds to the value computed from an approximate algorithm [START_REF] Masson | Slack time evaluation with rtsj[END_REF].When just one line is represented, the value estimated by the approximate algorithm is the same as the value computed by the exact algorithm. We remark that the approximation offers good results with regard to the exact value. To provide the better efficiency, we must power down the processor as few as possible because the restarting process represents a non-negligible cost. We remark that there is peak values for the Slack and they occur when a task is finished. To compute the Slack, the algorithm considers the current deadline of the active tasks. But when a task finished, the algorithm considers its next deadline. So we can say that a finished task reload the Slack. The approximate algorithm updates the Slack estimation at the beginning and at the end of each task. So we know at the end of each task if we have enough Slack to power down the processor and restart it without tasks miss their deadline. We compare in Figure 4 the average length of an idle times function of a power down threshold. 10 systems of 10 tasks has been generated; each system has a CPU load of 80%, so 20% of time is idle.

The simulations go on 800 seconds. We compare 3 methods to exploit idle times. The first method is a background task with a priority lesser than all other tasks. We show that the idle times have a very short length compared with other methods. The reason is that the idle times are scattered. The polling server is a better solution because a task is allowed and this task consume the maximum possible time. But it doesn't take advantage of all idle times. Therefore, the Slack appears as the better solution here. Indeed it aggregates idle times by delaying the task. We compare in Figure 5 the total length of sleeping periods function of a power down threshold. The same parameters of simulation as previously has been used except that the CPU load was take the values 40%, 60% and 80%. We show that the total time during which the processor can be powered down is longer when we use Slack algorithm than when we use other methods. An exception occurs when the system is very loaded and the suspend threshold is small. But we can consider that this situation is critical and it is not acceptable in our application context. We show by these results that we can optimize the power saving of a processor by aggregating idle times using an approximate Slack algorithm. If we consider that to start a idle processor represents a non-negligible cost, this solution can be a good alternative to passive power saving.

Conclusions

We presented in this paper a model to abstract a sensor node. We used this model to consider a sensor node as a real-time system. We proposed different methods to manage idle period in such systems and power down the processor during this period. We proposed to aggregate this idle period to increase the period of cutting off using slack stealer algorithms. After the presentation of different slack stealer algorithms, we proposed to use a approximate algorithm and we explained when power down the processor. Finally, we presented results of simulation which show the viability of our assumptions.

This first study of sensor model (in terms of acquisition and processing) allowed us to go to the decentralization of sensors signal processing in order to increase the system reliability and in the same have a good energy autonomy.

Future Work

We have to implement this solution on real time embedded sensors to perform measures on a real system. A first step will be to consider a single sensor and validate the solution. A second step could be to find a distributed solution for the wireless ad-hoc sensor networks. If the sensors communicate with a sink, they can be turned off without impact on the connexity of the network. But in an ad-hoc network, we can power down a node only if the graph stay connected.

Figure 2 .

 2 Figure 2. The sensor is powered down during idle times : a) without Slack management, b) with Slack management.

Figure 3 .

 3 Figure 3. A system of 3 tasks with the associated slack at each instant.

Figure 4 .

 4 Figure 4. Average length of an idle times.

Figure 5 .

 5 Figure 5. Total length of sleeping period.

http://quovadis.ibisc.univ-evry.fr/

Acknowledgments

The authors gratefully acknowledge the contribution of French National Research Association (ANR) in the framework of the QuoVADis Project.