Joonatan Jalonen

Jarkko Kari

On Dynamical Complexity of Surjective Ultimately Right-Expansive Cellular Automata

We prove that surjective ultimately right-expansive cellular automata over full shifts are chain-transitive. This immediately implies Boyle's result that expansive cellular automata are chain-transitive. This means that the chain-recurrence assumption can be dropped from Nasu's result that surjective ultimately right-expansive cellular automata with right-sided neighborhoods have the pseudo-orbit tracing property, which also implies that the (canonical) trace subshift is sofic. We also provide a theorem with a simple proof that comprises many known results including aforementioned result by Nasu. Lastly we show that there exists a right-expansive reversible cellular automaton that has a non-sofic trace and thus does not have the pseudo-orbit tracing property. In this paper we only consider cellular automata over full shifts, while both Nasu and Boyle obtain their results over more general shift spaces.

Introduction

Questions regarding what kind of a subshift an expansive cellular automaton is conjugate to has been considered at least in [START_REF] Nasu | Textile systems for Endomorphisms and Automorphisms of the Shift[END_REF][START_REF] Kůrka | Languages, equicontinuity and attractors in cellular automata[END_REF][START_REF] Blanchard | Dynamical properties of expansive one-sided cellular automata[END_REF][START_REF] Boyle | Expansive invertible onesided cellular automata[END_REF][START_REF] Nasu | The Dynamics of Expansive Invertible Onesided Cellular Automata[END_REF][START_REF] Nasu | Textile systems and one-sided resolving automorphisms and endomorphisms of the shift[END_REF]. In [START_REF] Nasu | Textile systems for Endomorphisms and Automorphisms of the Shift[END_REF] Nasu presented his textile systems and used them to show that positively expansive two-sided cellular automata are conjugate to full shifts. Around the same time, using more standard methods of symbolic dynamics, Kůrka [START_REF] Kůrka | Languages, equicontinuity and attractors in cellular automata[END_REF] obtained independently that positively expansive cellular automata are conjugate to subshifts of finite type. Kůrka explicitly stated this only for two-sided cellular automata but the proof also works for one-sided positively expansive cellular automata. Blanchard and Maass [START_REF] Blanchard | Dynamical properties of expansive one-sided cellular automata[END_REF] improved the case of positively expansive one-sided cellular automata and showed that these are conjugate to full shifts. Next Nasu [START_REF] Nasu | The Dynamics of Expansive Invertible Onesided Cellular Automata[END_REF], again using textile systems, proved that one-sided expansive cellular automata are conjugate to subshifts of finite type. Later on Nasu [START_REF] Nasu | Textile systems and one-sided resolving automorphisms and endomorphisms of the shift[END_REF] proved that also expansive two-sided cellular automata are conjugate to subshifts of finite type if the local neighborhood is one-sided. In this Nasu used Boyle's result from [START_REF] Boyle | Some sofic shifts cannot commute with nonwandering shifts of finite type[END_REF] that expansive cellular automata are chain-transitive. Using an additional assumption to guarantee chain-transitivity Nasu extended his result for two-sided surjective ultimately right-expansive cellular automata with right-sided neighborhoods. By ultimately right-expansive we mean that if we know with finite precision the entire history and future of a point, then we know the entire right side of the space-time diagram.

In this paper we restrict to cellular automata over full shifts. We show that a surjective ultimately right-expansive cellular automaton is automatically chaintransitive (Theorem 1). The proof is elementary. It then follows that one of Nasu's assumptions can be dropped, at least for cellular automata over full shifts. We will also provide a single theorem (Theorem 2), with a simple proof, that covers many of the cases mentioned in the previous paragraph (for full shifts). The proof is inspired by Taati's proof that a cellular automaton that is reversible over its limit set is stable, i.e. reaches the limit set in finite time [START_REF] Taati | Cellular automata reversible over limit set[END_REF].

Lastly we show that the requirement of right-expansivity alone is not enough: We give an example of a right-expansive cellular automaton over a full shift with a trace that is not sofic. This is directly based on the construction of the second author and Lukkarila [START_REF] Kari | Some Undecidable Dynamical Properties for One-Dimensional Reversible Cellular Automata[END_REF]. In the case of cellular automata over non-transitive subshifts, the appendix of [START_REF] Boyle | Some sofic shifts cannot commute with nonwandering shifts of finite type[END_REF] contains an example by Fiebig of an expansive cellular automaton over a non-transitive subshift whose trace is not an SFT.

Preliminaries

Notations For two integers i, j ∈ Z such that i < j the interval from i to j is denoted [i, j] = {i, i + 1, . . . , j}. We also denote [i, j) = {i, i + 1, . . . , j -1} and (i, j] = {i + 1, . . . , j}. Notation M is used when it does not matter whether we use N or Z. Composition of functions f : X → Y and g : Y → Z is written as gf and defined by gf (x) = g(f (x)) for all x ∈ X.

Topological dynamics A (topological) dynamical system is a pair (X, f ) where X is a compact metric space and f a continuous map X → X. Let (X, f ) and (Y, g) be two dynamical systems. A continuous map φ :

X → Y is a homomor- phism if φf = gφ. If φ is surjective, it is a factor map, and (Y, g) is a factor of (X, f ). Let d : X × X → R + ∪ {0} be the metric considered. A sequence (x i ) i∈Z is an orbit of f if f (x i ) = x i+1 for every i ∈ Z. Let x, y ∈ X.
There is an ε-chain from x to y if there exists n > 0 and a sequence x = x 0 , x 1 , . . . , x n = y ∈ X such that d(f (x i ), x i+1 ) < ε, for all i ∈ {0, 1, . . . , n -1}. Infinite ε-chains are called ε-pseudo-orbits. The dynamical system (X, f )

-is transitive if for all non-empty open sets U, V there exists n > 0 such that F n (U ) ∩ V = ∅.
is chain-recurrent if for all x ∈ X and ε > 0 there exists an ε-chain from x to x. is chain-transitive if for all x, y ∈ X and ε > 0 there exists an ε-chain from

x to y. has pseudo-orbit tracing property, often also called the shadowing property, if for all ε > 0 there exists δ > 0 such that for any δ-pseudo-orbit (x i ) i∈Z there exists an orbit (y i ) i∈Z such that d(x i , y i ) < .

Symbolic dynamics The set of infinite sequences over an alphabet

A indexed by M is A M . An element c ∈ A M is a configuration. A configuration is a function M → A and we denote c(i) = c i for i ∈ M. Let D ⊆ M be finite and u ∈ A D , then the set [u] = {c ∈ A M | c D = u} is called a cylinder.
Let A have the discrete topology and A M the product topology. Cylinders form a countable clopen (open and closed) base of this topology. We consider A M to be a metric space with the metric

d(c, e) = 2 -min({|i||ci =ei}) , if c = e 0, if c = e
for all c, e ∈ A M . It is well-known that this metric induces the same topology as defined above, and that this space is compact. For any n ∈ N \ {0} we denote A n = A [0,n) , and A + = n∈N\{0} A n and call any subset L ⊂ A + a language. The language L is finite if L is finite, and regular if it is recognized by a finite state automaton.

If L 1 , L 2 ⊆ A + are two languages, then their concatenation is L 1 L 2 = {uv ∈ A + | u ∈ L 1 and v ∈ L 2 }.
The shift map σ : A M → A M , defined by σ(c) i = c i+1 for all i ∈ M, is continuous. The dynamical system (A M , σ) is the full (A-)shift. A dynamical system (X, σ), where X ⊆ A M is non-empty, topologically closed, and σ m (X) ⊆ X for all m ∈ M, is a shift space or a subshift. When it does not cause confusion, we will simply talk about a subshift X.

A configuration c ∈ A M avoids u ∈ A n if σ i (c) [0,n) = u for all i ∈ M, otherwise u appears in c. Let S ⊆ A + ,
and let X S be the set of configurations that avoid S, i.e. X S = {c ∈ A M | ∀u ∈ S : c avoids u}. It is well-known that the given topological definition of subshifts is equivalent to saying that there exists a set of forbidden words S such that X = X S . If there exists a finite set S such that X = X S , then X is a subshift of finite type (SFT). If Y is a factor of an SFT, then it is a sofic shift. An equivalent characterization of sofic shifts is that the set of forbidden words is a regular language.

The language of a subshift (X, σ) is the set of words that appear in some configuration of X, and is denoted by L(X). We also denote L n (X) = L(X)∩A n the set of words of length n that appear in X. The subshift (X, σ) is transitive if and only if for every u, v ∈ L(X) there exists w ∈ L(X) such that uwv ∈ L(X). The entropy of (X, σ) is the exponential growth rate of the number of appearing words as the length of the words increases:

h(X, σ) = lim n→∞ 1 n log 2 (|L n (X)|).
We only need the following facts about entropy.

Proposition 1 ([13, Proposition 4.1.9.]). Let X and Y be subshifts and F : X → Y a factor map. Then h(Y, σ) ≤ h(X, σ).

Proposition 2 ([13, Corollary 4.4.9.]). Let X be a transitive sofic shift and Y ⊆ X a subshift. If Y = X, then h(Y, σ) < h(X, σ).

Cellular automata A cellular automaton (CA) is a dynamical system (A M , F ) where F is a shift-commuting map, i.e. F σ = σF . When M = N, the CA is called one-sided and when M = Z, the CA is called two-sided. We will often refer to a CA by the function name alone, i.e. talk about the CA F . The CA F is reversible if there exists another CA

F such that F F (c) = c = F F (c) for all c ∈ A M . Let D = [i, j] ⊂ M and let G loc : A D → A. Define G : A M → A M by G(c) i = G loc ((σ i (c)) D ).
Then G is continuous and commutes with σ, so it is a cellular automaton. The set D is a local neighborhood of G and the function G loc is a local rule of G. According to the Curtis-Hedlund-Lyndon Theorem every CA is defined by a local rule. Let m, a ∈ Z be the smallest numbers such that G is defined by a local rule on A [-m,a] , then m is the memory, a the anticipation, and r = max{a, m} the radius of G. If m ≤ 0 then G is memoryless. We overload the notation for the global function and use it also on finite words: For any n > 2r and u ∈ A n we define in a natural way the word G(u) ∈ A n-2r . For a CA (A Z , F ) the space-time diagrams are the two-way infinite orbits denoted as

st(F ) = {(c (i) ) i∈Z ∈ (A Z ) Z | ∀i : F (c (i) ) = c (i+1) }.
As a pictorial presentation we consider these as coloured square lattices where rows are the points of the orbit and time advances downwards; left, right, up, and down should be understood accordingly. Notice that our space-time diagrams present bi-infinite orbits, so only the configurations in the limit set Λ F = n∈N F n (A Z ) of F are considered. However our results will be for surjective cellular automata, in which case Λ F = A Z .

Let (A M , F ) be a CA. Then F is positively expansive if there exists ε > 0 such that ∀c, e ∈ A M : c = e =⇒ ∃n ∈ N : d(F n (c), F n (e)) > ε .

(

) 1
If F is reversible, then F is expansive if there exists ε > 0 such that ∀c, e, ∈ A M : c = e =⇒ ∃n ∈ Z : d(F n (c), F n (e)) > ε . ( 2
)
If F is reversible and

M = Z, then F is right-expansive if there exists ε > 0 such that ∀c, e ∈ A Z : ∃i > 0 : c i = e i =⇒ ∃n ∈ Z : d(F n (c), F n (e)) > ε . (3)
Left-expansive and positively right/left-expansive are defined analogously.

Remark 1. A one-sided cellular automaton (A N , F ) can be naturally extended to a memoryless two-sided cellular automaton (A Z , F ). One should be slightly careful with this: Firstly notice that F may be reversible over A Z but nonreversible over A N , for example the shift map. (However if F is reversible over A N , then its extension to A Z is also reversible.) Secondly, if (A N , F ) is expansive, then (A Z , F ) is right-expansive (but never expansive). Similarly for positively expansive cellular automata.

Ultimate expansivity and trace subshifts

We generalize the concept of expansivity to possibly non-reversible cellular automata. A cellular automaton (A Z , F ) is ultimately expansive if there exists ε > 0 such that

∀(c (i) ) i∈Z , (e (i) ) i∈Z ∈ st(F ) : c (0) = e (0) =⇒ ∃n ∈ Z : d(c (n) , e (n) ) ≥ ε
Ultimately right-expansive and ultimately left-expansive are defined the same way. The set of ultimately expansive cellular automata contains the expansive cellular automata, the positively expansive cellular automata, and more.

Example 1. A cellular automaton (A Z , F ) is nilpotent if there exists q ∈ A and n ∈ N such that for every c ∈ A Z we have that F n (c) = • • • qqq • • • . Then τ (F )
is a singleton and it follows that F is ultimately expansive.

There cannot be a reversible cellular automaton that would be ultimately expansive but not expansive, as ultimate expansivity and reversibility together imply expansivity. However there are surjective ultimately expansive cellular automata which are neither expansive nor positively expansive:

Example 2. Let A = {0, 1} , σ : A Z → A Z be the shift map and X : A Z → A Z be the xor-CA, that is the CA defined by X loc : A [-1,1] → A, X loc (abc) = a ⊕ c,
where ⊕ denotes addition modulo 2. The shift map σ is expansive, and so also ultimately expansive. The xor-CA cannot be expansive as it is not reversible, however it is positively expansive, and so also ultimately expansive. Consider the direct product of these, that is the CA σ × X :

A Z × A Z → A Z × A Z defined by σ × X (c, e) = (σ(c), X (e))
. This is neither expansive (not even reversible) nor positively expansive (since σ is not). However σ × X is ultimately expansive.

In what follows we will consider configurations of (A n ) Z where n > 0, which can lead to indexing issues. To avoid these issues we define for every n ∈ N \ {0}, i ∈ {0, . . . , n -1}, and j ∈ {0, . . . , i} projection functions π i :

A n → A and π [i,j] : A n → A j-i+1 where π i (a 0 • • • a n-1 ) = a i and π [i,j] (a 0 • • • a n-1 ) = a i • • • a j .
We also extend these to (A n ) Z cell-wise.

Let (A Z , F ) be a cellular automaton with radius r. The n-trace of F is the two-sided subshift of columns of width n that appear in the space-time diagrams of F , i.e.

τ n (F ) = t ∈ (A n ) Z | ∃(c (i) ) i∈Z ∈ st(F ) : ∀j ∈ Z : t j = c (j) [0,n)
Since we are mainly interested in the 2r-trace, we denote τ (F ) = τ 2r (F ) and call it the trace of F . Notice that our traces are always two-sided subshifts, which is in line with our definition of space-time diagrams: Traces are vertical stripes of space-time diagrams.

A cellular automaton (A Z , F ) is ultimately right-expansive if and only if there exists n ∈ N such that for all (c (i) ) i∈Z , (e (i) ) i∈Z ∈ st(F ) it holds that ∀j ∈ {0, . . . , 2n} : c

(j) [0,2r) = e (j) [0,2r) =⇒ c (n) 2r = e (n) 2r . (4)
2r So for an ultimately right-expansive F we can define a CA ((

A 2r ) Z , - → F ) such that for every t ∈ τ (F ) we have that - → F (t) ∈ τ (F ) is the unique configuration such that π [1,2r) (t) = π [0,2r-1) ( - → F (t)
) and the last column of -→ F (t) is the column defined by (4) (Figure 1). How -→ F maps the words that do not appear in τ (F ) is irrelevant for us. Then {(π 0 (

- → F i (t))) i∈N | t ∈ τ (F )} is the set of right halves of st(F ).
Next we consider ε-chains for cellular automata. Let (A Z , F ) be a CA. For every n ∈ N \ {0} we define a directed labeled multigraph G n (F ) = (V n , E n ) as follows:

-The set of vertices is

V n = A n .
-For every u ∈ V n and x, y ∈ A r there is a labeled edge u

xy -→ F (xuy) in E n . The graph G n (F ) defines an SFT X n (F ) ⊆ (A n ) Z where (u, v) ∈ (A n ) 2 is for- bidden if there is no edge u -→ v.
The points of X n (F ) are essentially the pseudo-orbits of F . From the definitions we get a characterization of chain transitive CA's that is more convenient for us:

Proposition 3. A CA (A Z , F ) is chain-transitive if and only if X n (F ) is tran- sitive for every n. Proof. (A Z , F ) is chain-transitive ⇐⇒ ∀ε > 0 : ∀c, e ∈ A Z : ∃c = c (0) , . . . , c (n) = e : d(F (c (i) ), c (i+1) ) < ε ⇐⇒ ∀k ∈ N : ∀c, e ∈ A Z : ∃c = c (0) , . . . , c (n) = e : F (c (i) ) [-k,k] = (c (i+1) ) [-k,k] ⇐⇒ ∀k ∈ N : G k (F ) is strongly connected ⇐⇒ ∀k ∈ N : X k (F ) is transitive.
For every n ≥ 2r and i ∈ {0, . . . , n-2r} we denote Σ i,n (F ) = π [i,i+2r) (X n (F )). Subshifts Σ i,n (F ) are sofic as factors of SFTs. The elements of Σ i,n (F ) can be considered as such configurations that can be extended with i columns to the left and with n-i-2r columns to the right without introducing violations of the local rule of F . Our chief interest are the middle columns, that is the subshifts Σ n-r,2n (F ), so we denote them by Σ n (F ) and call them approximations of the trace. We simplify the notations and omit the name of the CA when it is clear from the context.

We notice that the approximations Σ n coincide with τ (F ) in the limit:

Proposition 4. Let (A Z , F ) be a surjective CA with radius r. Then τ (F ) = n≥r Σ n .
Proof. "⊆": If t ∈ τ (F ) then any space-time diagram that contains t shows that t ∈ Σ n for every n ∈ N where n ≥ r. "⊇": Let t ∈ n≥r Σ n , and suppose that t / ∈ τ (F ). Then t must contain some forbidden word of the subshift τ (F ), i.e. there exists i, j ∈ Z such that t [i,j] / ∈ L(τ (F )). But this is a contradiction, since L k (Σ kr ) = L k (τ (F )) for all k ∈ N.

The pseudo-orbit tracing property has the following characterization for cellular automata.

Proposition 5. Let (A Z , F ) be a surjective CA. Then F has the pseudo-orbit tracing property if and only if there exists n such that τ (F ) = Σ n .

Proof. "⇒": The pseudo-orbit tracing property immediately implies that there exists n ∈ N such that the set of middle columns of X 2n is τ (F ).

"⇐": If τ (F ) = Σ n then for any k and any x ∈ X 2k+2n there exists an orbit (c (i) ) i∈Z such that c

(i) [-k,k]
is the word of length 2k in the middle of x i for every i ∈ Z.

From this it follows that if F has the pseudo-orbit tracing property, then τ n (F ) is sofic for every n. This was already proved by Kůrka in [START_REF] Kůrka | Languages, equicontinuity and attractors in cellular automata[END_REF] where it was also proved that if every τ n (F ) is an SFT, then F has the pseudo-orbit tracing property.

We say that F has the left-extension property if there exists i and N such that ∀n ≥ N, m ≥ 0 :

Σ i,n = Σ i+m,n+m .
The right-extension property is defined analogously. From Proposition 5 we see that the extension properties are one-sided variants of the pseudo-orbit tracing property, i.e. that a cellular automaton has the pseudo-orbit tracing property if and only if it has both the right-and the left-extension property.

Remark 2. A memoryless CA F with neighborhood [0, r] has the left-extension property: Take any configuration t ∈ (A r ) Z and any a ∈ A. Define configurations (t (i) ) i∈N as follows:

t (i) j = aπ [1,r) (t j ), if j ≤ -i F loc (π 0 (t (i) j-1 )t j-1 )π [1,r) (t j ) if j > -i
. By compactness the sequence (t (i) ) i∈N has a converging subsequence (t (i) ) i∈I . Let the limit of this sequence be t . Now t is a configuration that shows that t can be extended with one column to the left. We can repeat the process to extend t to the left as much as we will. This shows that Σ 0,n = Σ m,n+m for all n ≥ r, m ≥ 0. Now the following corollary is immediate.

Corollary 1. If F is memoryless, then τ (F ) = i≥2r Σ 0,i .
Proof. From Remark 2 it follows that for all n ≥ r we have Σ 0,n = Σ n-r , and so the claim follows from Proposition 4.

Surjective ultimately right-expansive CA are chain-transitive

Consider a CA (A Z , F ). Let P = {A i } i∈{0,...,n-1} be a partition of A. We say that F respects P at x ∈ A Z if for every k ∈ N there exists j ∈ {0, 1, . . . , n -1} such that F k (x) ∈ A Z j . Let S be the set of all points where F respects P . This is a subshift. Now we define a projection ι :

(A Z ) N → (({0, 1, . . . , n -1}) Z ) N by ι(c) i,j = k if c i,j ∈ A k .
Next we project the forward orbits of S cell-wise using ι. According to the definition of S, each row is constant after this mapping, so we can consider the projected forward orbits as a one-sided one-dimensional subshift over the alphabet {0, 1, 2, . . . , n -1}. We will call this subshift the stripe trace of F with respect to P . Lemma 1. Let (A Z , F ) be a CA and P = {A i } i∈{0,...,n-1} a non-trivial partition of A. The stripe trace of F with respect to P cannot be the full shift {0, 1, . . . , n-1} N .

Proof. We can simplify the situation and assume that the local rule of F is a function A [0,1] → A by composing F with a suitable power of the shift map and using a suitable grouping map g n :

A Z → (A n ) Z , (g n (c)) i = c in c in+1 • • • c in+n-1 .
This can be done since shifting does not change the stripe trace and we can define a partition of the grouped alphabet that gives the same stripe trace. We may also assume that our partition is {A 0 , A 1 }.

Suppose that the stripe trace of F is the full shift {0, 1} N . Let S be the set of configurations that respect the partition {A 0 , A 1 }. For every l ∈ N \ {0} and u ∈ {0, 1} l we denote

S u = {v ∈ L l (S) | F j (v) 0 ∈ A uj for all j ∈ {0, . . . , l -1}}.
Since the stripe trace is the full shift, all of these S u sets must be non-empty. Let |A| = k. We will show that no matter how large k is, it will not be large enough.

Let u, v ∈ A l for some l ∈ N \ {0}. Now consider a word w ∈ S uv . Let w = w w where w , w ∈ A l . From the definition of S uv we have that both w and w must be in S u , so we have S uv ⊆ S u S u and so

v∈A l S uv ⊆ S u S u .
From this we get the inequality v∈A l |S uv | ≤ |S u | 2 , and then we have that min

v∈A l |S uv | ≤ |S u | 2 2 l . ( 5
)
From this we get an upper bound for the size of the smallest set S u1•••u 2 n for every n ∈ N:

min u1u2•••u 2 n ∈A 2 n |S u1u2•••u 2 n | ≤ z n ,
where z n is defined by the recursive formula

z n+1 = z 2 n 2 2 n , z 0 = k 2 .
We get this from the fact that min{|S 0 |, |S 1 |} ≤ k 2 , and then using inequality [START_REF] Grünbaum | Tilings and patterns[END_REF]. Solving this recursion yields

z n = k 2 n 2 2 n +n•2 n-1 .
But now we see that the sequence (z n ) n∈N converges to zero, and so for some N ∈ N and u ∈ {0, 1} N we have that S u = ∅ which proves the claim.

Since subshifts with only periodic points are finite, one can easily obtain these as stripe traces by using only uniform configurations. Using the infinite firing squad CA [START_REF] Kari | Rice's theorem for the limit sets of cellular automata[END_REF] we see that also the sunny side up subshift, i.e. {c ∈ {0, 1} N | c has at most one 1}, is a stripe trace of a CA. There are some more or less trivial generalizations of these examples. We also have an example of a stripe trace configuration that is not eventually periodic. However we believe, for basically the same reason as why the full shift cannot be a stripe trace, that stripe traces always have zero entropy.

While the stripe trace has certain interest in itself, we just need the above lemma as a technical detail in the following.

Theorem 1. A surjective ultimately right-expansive CA (A Z , F ) is chain-tran- sitive.
Proof. According to Proposition 3, we can equally well show that the subshifts X n (F ) are transitive, i.e. that their defining graphs G n (F ) are strongly connected. Clearly if X n (F ) is transitive, then so is X k (F ) for any k < n so we can assume that n ≥ 2r.

Let us remind that the vertex set of G n (F ) is V = A n and that we have an edge u xy -→ v if and only if F (xuy) = v, where x, y ∈ A r . Let deg in (u) denote the number of incoming edges to the vertex u and deg out (u) the number of outgoing edges from the vertex u. By definition we have that deg out (u) = |A| 2r for every u ∈ V . By the balancedness property of surjective CA's [START_REF] Maruoka | Condition for Injectivity of Global Maps for Tessellation Automata[END_REF] we also have that deg in (u) = |A| 2r for every u ∈ V . It is well-known that deg in (u) = deg out (u) for every u ∈ V if and only if the graph is a union of Eulerian graphs, that is graphs which have a directed path (sequence of edges traversed in the direction of the edges) where every edge appears exactly once, and which starts and ends at the same vertex. Especially we have that there are no edges between the strongly connected components of G n (F ).

Let G n (F ) 1 , G n (F ) 2 , . . . , G n (F ) m be the strongly connected components of G n (F ) and V 1 , . . . , V m ⊆ A n the corresponding vertex sets. Now {V i } i∈{1,...,m} is a partition of A n . There are no edges between the strongly connected components which means that the pseudo-orbits cannot go from a cylinder of the set V i to a cylinder of the set V j for any i = j. Then definitely the orbits cannot do this either, and so we have that τ n (F ) ⊆ i∈{1,...,m} V Z i . Notice that we have not yet used the ultimate right-expansivity, so everything said thus far holds for surjective cellular automata in general. Since F is ultimately rightexpansive we have a cellular automaton ((

A n ) Z , - → F n ) which is just a natural extension of ((A 2r ) Z , - → F
). Now we consider the cellular automaton -→ F n n , so that the preimages and images are not overlapping stripes of space-time diagrams. Each of these stripes is contained in

V Z i for some i ∈ {1, . . . , m}. If m > 1 then - → F n n and the partition {V i } {1,...,m} would contradict Lemma 1: Take an arbitrary c ∈ (A n ) Z = i∈{1,...,m} V i Z . Let s c ∈ st(F ) be such that c is a row in s c . Now applying - → F n
n to a stripe of width n in s c shows that we can draw an arbitrary stripe trace configuration over {1, . . . , m} with -→ F n n . Notice that the way we complete -→ F to the full shift is irrelevant since this can only grow the stripe trace. This concludes the proof. This has the following immediate corollary.

Corollary 2. Let (A Z , F ) be a surjective ultimately right-expansive CA. Then Σ i,n (F ) is transitive for every i, n ∈ N such that i ≤ n -2r.

Proof. According to Proposition 1 we have that X n (F ) is transitive for every n ∈ N. The claim follows immediately since a factor of a transitive system is also transitive.

Traces of expansive cellular automata

Next we provide an elementary proof that surjective ultimately right-expansive cellular automata with the left-extension property have the pseudo-orbit tracing property. This is almost the same result as Nasu's [START_REF] Nasu | Textile systems and one-sided resolving automorphisms and endomorphisms of the shift[END_REF]Theorem 6.3]. The main differences are that our proof is only for cellular automata over full shifts while Nasu's is over transitive SFT's, and on the other hand that Nasu has an additional assumption of chain-recurrence, which Nasu uses to guarantee chaintransitivity.

Theorem 2. Let (A Z , F ) be a surjective ultimately right-expansive CA with the left extension property. Then F has the pseudo-orbit tracing property and τ (F ) is a transitive sofic shift. If F is memoryless, then τ (F ) is an SFT.

Proof. We have seen that Σ l (F ) is a sofic shift for every l ∈ N, and according to Corollary 2 it is also transitive. We will show that there exists m ∈ N such that τ (F ) = Σ m .

Let i, N ∈ N be given by the left-extension property, so that for all n ≥ N and m ≥ 0 we have that Σ i,n = Σ i+m,n+m . Let -→ F : (A 2r ) Z → (A 2r ) Z be a cellular automaton defined by the ultimate right-expansivity of F (how -→ F maps words that do not appear in τ (F ) is irrelevant). As L(Σ kr ) = L k (τ (F )) we have that there exists m such that -→ F is defined on Σ m . Let m ≥ max{m , N -i}.

Claim:

- → F (Σ m ) = Σ m-1 . Proof: "⊆": Let t (0) ∈ Σ m . Since t (0)
is the central stripe of some element in X m (F ) there is a t (1) ∈ Σ m-r+1,2m ⊆ Σ m-1 such that t (0,1) ∈ (A 2r+1 ) Z defined by π [0,2r) (t (0,1) ) = t (0) and π [1,2r] (t (0,1) ) = t (1) has no violations of the local rule of F . But then it has to be that -→ F (t (0) ) = t (1) .

"⊇": Now let t (1) ∈ Σ m-1 . By the left-extension property we have that t (1) ∈ Σ m-r+1,2m , so that there exists t (0) ∈ Σ m such that -→ F (t (0) ) = t (1) . Now we have that Σ m-1 is a factor of Σ m , so Σ m-1 has at most the entropy of Σ m (Proposition 1). But we also have that Σ m ⊆ Σ m-1 , and so Σ m and Σ m-1 have the same entropy. Since Σ m-1 is a transitive subshift, all its proper subshifts have strictly smaller entropy (Proposition 2), and so it follows that Σ m = Σ m-1 . Let l = max{m , N -i} and we have τ (F ) = Σ l . Now F has the pseudo-orbit tracing property according to Proposition 5.

It is left to show that if F is memoryless, say with neighborhood [0, r], then τ (F ) is an SFT. According to Corollary 1 we now have that Σ 0,k+r = τ (F ) for some k. Let the radius of -→ F be z. Apply -→ F to the words u ∈ (A r ) k•2z+1 for k times. If no violations of the local rule of F appears, then u ∈ L(Σ m ) = L(τ (F )). On the other hand, if a violation does appear, then u / ∈ L(τ (F )). We get a finite set of forbidden words that defines τ (F ).

Remark 3. Theorem 2 implies the following:

-If (A N , F ) is surjective and positively expansive, then τ (F ) is an SFT ( [START_REF] Kůrka | Languages, equicontinuity and attractors in cellular automata[END_REF],

improved in [START_REF] Blanchard | Dynamical properties of expansive one-sided cellular automata[END_REF]) -If (A N , F ) is reversible and expansive, then τ (F ) is an SFT ( [START_REF] Nasu | The Dynamics of Expansive Invertible Onesided Cellular Automata[END_REF]) -If (A Z , F ) is reversible, (right-)expansive, and memoryless, then τ (F ) is an SFT ( [START_REF] Nasu | Textile systems and one-sided resolving automorphisms and endomorphisms of the shift[END_REF]).

6 Right-expansive cellular automaton with non-sofic trace

Next we show that while it might be possible to replace the assumption of left-extension property in Theorem 2 with a weaker assumption, it can not be dropped entirely. Using the construction from [START_REF] Kari | Some Undecidable Dynamical Properties for One-Dimensional Reversible Cellular Automata[END_REF] we give an example of a rightexpansive CA that has a non-sofic trace. The next paragraphs summarizes what we need, but for a more detailed presentation we refer the reader to [START_REF] Kari | The nilpotency problem of one-dimensional cellular automata[END_REF], [START_REF] Kari | Some Undecidable Dynamical Properties for One-Dimensional Reversible Cellular Automata[END_REF], and [START_REF] Lukkarila | The 4-way deterministic tiling problem is undecidable[END_REF]. Notice that our example is over a full shift, which in particular is a transitive subshift; an example by Fiebig of an expansive cellular automaton over non-transitive subshift was already presented in the appendix of [START_REF] Boyle | Some sofic shifts cannot commute with nonwandering shifts of finite type[END_REF].

A set of Wang tiles T is a set of squares with each edge coloured with a colour from a finite colour set A. Let us fix that (x, y, z, w) ∈ A 4 is a Wang tile such that the colours are presented in the order W-N-E-S (west-north-east-south). A tiling by T is an assignment Z 2 → T . A tiling is valid if the adjacent edges have the same colour. The set T is called NW-deterministic if for all a, b ∈ A we have that |{a}×{b}×A×A∩T | ≤ 1. Other XY-determinism's are defined analogously. If T is both NW-and SE-deterministic, then T is called two-way deterministic. Any two-way deterministic tile set can be completed in the sense that we can add tiles T C so that for all a, b ∈

A holds that |{a} × {b} × A × A ∩ (T ∪ T C )| = 1 = |A×A×{a}×{b}∩(T ∪T C )|.
This can be done since we must be missing the same number of NW-and SE-pairs; in T C we just match these arbitrarily. This means that a two-way deterministic set of Wang tiles T can be used to define a reversible cellular automaton F T : (T ∪ T C ) Z → (T ∪ T C ) Z where configurations represent SW-NE-diagonals of valid tilings with T ∪ T C .

A tiling c by a Wang tile set T is periodic if there exits (x, y) ∈ Z 2 \ {(0, 0)} such that for every (i, j) ∈ Z 2 we have that c i,j = c i+x,j+y . A Wang tile set T is aperiodic if it admits a valid tiling, but none of the valid tilings is periodic. We need the fact that there exists an aperiodic two-way deterministic Wang tile set. Such do exist: The Wang tile set derived from Amman's aperiodic tile set [START_REF] Grünbaum | Tilings and patterns[END_REF] is such, and the tile set constructed in [START_REF] Lukkarila | The 4-way deterministic tiling problem is undecidable[END_REF] is even 4-way deterministic. Details of the chosen tile set are irrelevant for us. Proposition 6. There exists a right-expansive cellular automaton with a nonsofic trace.

Proof. Following paragraph shortly describes what we get from a construction in [START_REF] Kari | Some Undecidable Dynamical Properties for One-Dimensional Reversible Cellular Automata[END_REF]:

Let T be a two-way deterministic aperiodic set of Wang tiles. Define F T : (T ∪ T C ) → (T ∪ T C ) as above; the tiles in T C are considered to be tiling errors. For large enough k it holds that

σ k F T is expansive. Denote F = σ k F T . Next signals are added: Let G : ((T ∪ T C ) × {0, 1} 2 ) Z → ((T ∪ T C ) × {0, 1} 2 ) Z
where the tiling-layer is mapped by F and the signal layer is mapped as illustrated by Figure 2. As noted in [START_REF] Kari | Some Undecidable Dynamical Properties for One-Dimensional Reversible Cellular Automata[END_REF] this G is right-expansive and further has the property that if there is a tiling error somewhere, then every column right of the tiling error will contain both zero-and one-signals. Let r be the radius of G and suppose that τ (G) is sofic. Take a spacetime diagram which on the tiling-layer contains only states from T and on the signal-layer all the signals are zeroes. Such exists as T admits valid tilings and then setting every signal to zero will give a suitable space-time diagram. Let t ∈ (T × {(0, 0)}) 2r Z be a column of this space-time diagram. By soficness it follows that there exists

i ∈ Z, n ∈ N such that u = t [i,i+n) is such that • • • uuu • • • ∈ τ (G)
. Now since the tiling-layer is expansive, this implies that in the space-time diagram that has • • • uuu • • • as a column, the tiling layer must be periodic. But since T is an aperiodic tile set, it then has to be that there are tiling errors densely; that is to say that there exists m ∈ N such that every m×m square in the space-time diagram has a cell whose tiling-layer is in a state from T C . In particular there has to be tiling errors left of the column • • • uuu • • • . But this is a contradiction, since if there is a tiling error left of the column, then the column's signal-layer has both zeroes and ones, but • • • uuu • • • has only zeroes.

Conclusion

To conclude let us give some overview of what is known and what is still open. Two main concepts we considered were ultimate expansivity and the pseudoorbit tracing property. For one-dimensional cellular automata these concepts have one-sided variants, namely left-and right-expansivity, and left-and rightextension property. In this setting we have asked what can be said about the trace of a cellular automaton assuming different combinations of expansivity and extension properties. For surjective cellular automata the following are known:

-If F has both the left-and the right-extension property, then the trace of F is sofic (from definitions).

-If F has the left-extension property and is right-expansive, then the trace of F is sofic (Theorem 2). -If F is right-expansive, then the trace of F is not necessarily sofic (Proposition 6).

-If F has the left-extension property, then F is not necessarily sofic (in [6, Example 1] an one-sided reversible cellular automaton with a non-SFT sofic trace was considered; we must omit the proof, but we can show that a small modification to that example gives a one-sided reversible cellular automaton with a non-sofic trace).

This list leads to some immediate questions: Is the trace of an ultimately expansive cellular automaton necessarily sofic, or an SFT? This is known to be the case for positively expansive cellular automata ( [START_REF] Kůrka | Languages, equicontinuity and attractors in cellular automata[END_REF], [START_REF] Nasu | Textile systems for Endomorphisms and Automorphisms of the Shift[END_REF]). Kůrka has conjectured that this would also be the case for expansive cellular automata [START_REF] Kůrka | Topological dynamics of one-dimensional cellular automata[END_REF]Conjecture 30]. It is clear that the left-extension property does not imply left-expansivity, as memoryless surjective CA's have the left-extension property but are not leftexpansive. However we do not know any example of a left-expansive cellular automaton that would not also have the left-extension property (for example the right-expansive CA of Proposition 6 also has the right extension property). Whether left-expansivity implies the left-extension property or not is interesting since if it does, then we have that the trace of a surjective ultimately expansive cellular automaton is sofic, and actually it is not difficult to see that it would be even an SFT.

Fig. 1 .

 1 Fig. 1. Ultimately right-expansive CA defines a CA -→ F which draws the (right halves) of the space-time diagrams. The figure illustrates how -→ F is defined; assuming that the grid has a valid space-time diagram of F , then -→ F maps the pattern in the light gray area to the pattern in the dark gray area.

Fig. 2 .

 2 Fig. 2. Here a, b ∈ {0, 1}, the light gray represents a tiling error, and ⊕ denotes addition modulo 2. The label of the arrow pointing to the lower left corner is the first bit and the label of the arrow pointing to the lower right corner is the second bit.


Jarkko Kari

Ville Salo

Thomas Worsch

Sequentializing Cellular Automata

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

Introduction

Cellular automata (CA) are models of parallel computation, so when implementing them on a sequential architecture, one cannot simply update the cells one by one -some cells would see already updated states and the resulting configuration would be incorrect. The simplest-to-implement solution is to hold two copies of the current configuration in memory, and map (x, x) → (x, G(x)) → (G(x), G(x)). This is wasteful in terms of memory, and one can, with a bit of thinking, reduce the memory usage to a constant by simply remembering a 'wave' containing the previous values of the r cells to the left of the current cell, where r is the radius of the CA.

Here, we study the situation where the additional memory usage can be, in a sense, dropped to zero -more precisely we remember only the current configuration x ∈ S Z , and to apply the cellular automaton we sweep a permutation χ : S m → S m from left to right over x (applying it consecutively to all length-m subwords of x). The positions where the sweep starts may get incorrect values, but after a bounded number of steps, the rule should start writing the image of the cellular automaton. We formalize this in two ways, with 'sliders' and 'sweepers', which are two ways of formally dealing with the problem that sweeps 'start from infinity'.

It turns out that the cellular automata that admit a sliding rule are precisely the ones that are left-closing (Definition 11), and whose number of right stairs (see Definition 14) of length 3m divides |S| 3m for large enough m. This can be interpreted as saying that the average movement 'with respect to any prime number' is not to the right. See Theorem 19 and Theorem 25 for the precise statements, and Section 4 for decidability results.

We introduce the sweeping hierarchy where left-to-right sweeps and rightto-left sweeps alternate, and the closing hierarchy where left-closing and rightclosing CA alternate. We show that the two hierarchies coincide starting from the second step. We do not know if the hierarchies collapse on a finite level.

Preliminaries

We denote the set of integers by Z. For integers i ≤ j we write [i, j) for {x ∈ Z | i ≤ x < j} and [i, j] for [i, j) ∪ {j}; furthermore [i, ∞) = {x ∈ Z | i ≤ x} and (-∞, i) = {x ∈ Z | x < i} have the obvious meaning. Thus [0, ∞) is the set of non-negative integers which is also denoted by N 0 .

Occasionally we use notation for a set M of integers in a place where a list of integers is required. If no order is specified we assume the natural increasing order. If the reversed order is required we will write M R .

For sets A and B the set of all functions f : A → B is denoted B A . For f ∈ B A and M ⊆ A the restriction of f to M is written as f | M or sometimes even f M . Finite words w ∈ S n are lists of symbols, e.g. mappings w : [0, n) → S. Number n is the length of the word. The set of all finite words is denoted by S * .

Configurations of one-dimensional CA are biinfinite words x : Z → S. Instead of x(i) we often write x i . We define the left shift σ : S Z → S Z by σ(x) i = x i+1 . The restriction of x to a subset (-∞, i) gives a left-infinite word for which we write x (-∞,i) ; for a right-infinite word we write x [i,∞) . These are called halfinfinite words. Half-infinite words can also be shifted by σ, and this is defined using the same formula. The domain is shifted accordingly so for

x ∈ S [i,∞) we have σ(x) ∈ S [i-1,∞) .
We use a special convention for concatenating words: Finite words 'float', in the sense that they live in S n for some n, without a fixed position, and u • v denotes the concatenation of u and v as an element of S |u|+|v| . Half-infinite configurations have a fixed domain (-∞, i] or [i, ∞) for some i, which does not change when they are concatenated with finite words or other half-infinite configurations, while finite words are shifted suitably so that they fill the gaps exactly (and whenever we concatenate, we make sure this makes sense).

More precisely, for w ∈ S * and y ∈ S (-∞,i] , we have y • w ∈ S (-∞,i+|w|] and for w ∈ S * and z ∈ S [i,∞) we have w • z ∈ S [i-|w|,∞) (defined in the obvious way). For a word w ∈ S * and half-infinite words y ∈ S (-∞,i) and z ∈ S [i+n,∞) we write y • w • z for the obvious configuration in S Z , and this is defined if and only if |w| = n.

The set S Z of configurations is assigned the usual product topology generated by cylinders. A cylinder defined by word w ∈ S n at position i ∈ Z is the set

[w] [i,i+n) = {x ∈ S Z | x [i,i+n) = w} of configurations that contain word w in position [i, i + n).
Cylinders are open and closed, and the open sets in S Z are precisely the unions of cylinders. We extend the notation also to half-infinite configurations, and define

[y] D = {x ∈ S Z | x D = y}. for D = [i, ∞) and D = (∞, i],
and any y ∈ S D . These sets are closed in the topology.

Because of a page limit for the submissions only some proofs are included in the version for the conference proceedings. An extended version with all proofs can be found on arXiv.org [START_REF] Kari | Sequentializing cellular automata[END_REF].

Sliders and sweepers

A block rule is a function χ : S m → S m . Given a block rule χ we want to define what it means to "apply χ from left to right once at every position". We provide two alternatives, compare them and characterize which cellular automata can be obtained by them. The first alternative, called a slider, assumes a bijective block rule χ that one can slide along a configuration left-to-right or right-toleft to transition between a configuration y and its image f (y). The second alternative, called a sweeper, must consistently provide values of the image f (y) when sweeping left-to-right across y starting sufficiently far on the left.

We first define what it means to apply a block rule on a configuration.

Definition 1. Let χ : S m → S m be a block rule and i ∈ Z. The application of χ at coordinate i is the function

χ i : S Z -→ S Z given by χ i (x) [i,i+m) = χ(x [i,i+m) ) and χ i (x) j = x j for all j ∈ [i, i + n). More generally, for i 1 , . . . , i k ∈ Z we write χ i1,...,i k = χ i k • • • • • χ i2 • χ i1 .
When m > 1, it is meaningless to speak about "applying χ to each cell simultaneously": An application of χ changes the states of several cells at once. Applying it slightly shifted could change a certain cell again, but in a different way.

We next define finite and infinite sweeps of block rule applications with a fixed start position.

Definition 2. Given a block rule χ for i, j ∈ Z, i ≤ j, define χ [i,j] = χ j •• • ••χ i ; analogously let χ [i,j) = χ j-1 • • • • • χ i .
For any configuration x ∈ S Z and fixed i ∈ Z the sequence of configurations x (j) = χ [i,j] (x) for j ∈ [i, ∞) has a limit (point in the topological space S Z ) for which we write χ i+ (x).

Analogously, for a block rule ξ the sequence of configurations x (j) = ξ [j,i) R (x) for j ∈ (-∞, i) has a limit for which we write ξ i-(x).

It should be observed that in the definition of χ i+ (x) one has i < j and the block rule is applied at successive positions from left to right. On the other hand j < i is assumed in the definition of ξ i-(x) and since the R in ξ [j,i) R indicates application of ξ at the positions in the reverse order, i.e. i -1, i -2, . . . , j, the block rule is applied from right to left. The reason the limits always exist in the definition is that the value of x (j) i changes at most m times, on the steps where the sweep passes over the cell i.

Example 3. Let S = {0, 1} and consider the block rule χ :

S [0,2) → S [0,2) : (a, b) → (b, a).
For consistency with the above definition denote by ξ the inverse of χ (which in this case happens to be χ again). Let s ∈ S and y ∈ S Z . We will look at the configuration x ∈ S Z with

x i =      y i+1 , if i < 0 s, if i = 0 y i , if i > 0
The application of χ successively at positions 0, 1, 2, . . . always swaps state s with its right neighbor. Since cell j can only possibly change when χ j-1 or χ j is applied, each cell enters a fixed state after a finite number of steps; see also the lower part of Figure 1 starting at the row with configuration x. 1. A sequence of configurations with the center cell at position 0. Starting with configuration x in the middle when going downward the swapping rule χ is applied to blocks [0, 1], [START_REF] Kari | Sequentializing cellular automata[END_REF][START_REF] Kari | Representation of reversible cellular automata with block permutations[END_REF], etc., and going from x upward rule ξ = χ is applied to blocks [-1, 0], [-2, -1] and so on.

ξ 0-(x) • • • y-3 y-2 y-1 y0 y1 y2 y3 • • • y . . . • • • ξ [-3,0) R (x) • • • s y-2 y-1 y0 y1 y2 y3 • • • ξ [-2,0) R (x) • • • y-2 s y-1 y0 y1 y2 y3 • • • ξ [-1,0) R (x) • • • y-2 y-1 s y0 y1 y2 y3 • • • x • • • y-2 y-1 y0 s y1 y2 y3 • • • x χ [0,1) (x) • • • y-2 y-1 y0 y1 s y2 y3 • • • χ [0,2) (x) • • • y-2 y-1 y0 y1 y2 s y3 • • • χ [0,3) (x) • • • y-2 y-1 y0 y1 y2 y3 s • • • . . . • • • χ 0+ (x) • • • y-2 y-1 y0 y1 y2 y3 y4 • • • z Fig.
Example 4. Let S = {0, 1} and consider the block rule χ : S [0,2) → S [0,2) : (a, b) → (a+b, b). Then sliding this rule over a configuration x ∈ {0, 1} Z produces the image of x in the familiar exclusive-or cellular automaton with neighborhood {0, 1} (elementary CA 102). We will see in Example 21 that the exclusive-or CA with neighborhood {-1, 0} can not be defined this way.

Definition of sliders

Definition 5. A bijective block rule χ with inverse ξ defines a slider relation

F ⊂ S Z ×S Z by (y, z) ∈ F iff for some x ∈ S Z and some i ∈ Z we have ξ i-(x) = y and χ i+ (x) = z. We call the pair (x, i) a representation of (y, z) ∈ F . Note that every (x, i) ∈ S Z × Z is a representation of exactly one pair, namely (ξ i-(x), χ i+ (x)) ∈ F . Lemma 6. Let (x, i) be a representation of (y, z) ∈ F under a bijective block rule χ of block length n. Then x (-∞,i) = z (-∞,i) and x [i+n,∞) = y [i+n,∞) .
Proof. Applying block rule χ at positions j ≥ i in x never changes cells at positions k < i. Therefore x k = (χ i+ (x)) k = z k proving the first part. The second part follows analogously.

Lemma 7. Let (y, z) ∈ F be fixed. For all i ∈ Z denote

R i = {x ∈ S Z | (x, i) is a representation of (y, z)}.
For i < j the function χ [i,j) : R i -→ R j is a bijection, with inverse ξ [i,j) R . All R i have the same finite cardinality.

Proof. The claim follows directly from the definition and the facts that

χ j+ • χ [i,j) = χ i+ and ξ j-• χ [i,j) = ξ i-, (1)
and that χ [i,j) and

ξ [i,j) R are inverses of each other. More precisely, if x ∈ R i then z = χ i+ (x) = χ j+ (χ [i,j) (x)) and y = ξ i-(x) = ξ j-(χ [i,j) (x)) so χ [i,j) (x) ∈ R j . This proves that χ [i,j) maps R i into R j .
This map is injective. To prove surjectivity, we show that for any x ∈ R j its preimage

ξ [i,j) R (x ) is in R i . Composing the formulas in (1) with ξ [i,j) R from the right gives χ j+ = χ i+ • ξ [i,j) R and ξ j-= ξ i-• ξ [i,j) R , so as above we get z = χ j+ (x ) = χ i+ (ξ [i,j) R (x )) and y = ξ j-(x ) = ξ i-(ξ [i,j) R (x )), as required.
The fact that the cardinalities are finite follows from Lemma 6: there are at most

|S| n choices of x [i,i+n) in x ∈ R i . Lemma 8. A slider relation F ⊂ S Z × S Z
defined by a bijective block rule χ is closed and shift-invariant, and the projections (y, z) → y and (y, z) → z map F surjectively onto S Z . Proof. By Lemma 7 every (y, z) ∈ F has a representation (x, 0) at position 0. Therefore, the relation F is closed as the image of S Z in the continuous map x → (ξ 0-(x), χ 0+ (x)).

Clearly (x, i) is a representation of (y, z) if and only if (σ(x), i -1) is a representation of (σ(y), σ(z)). Hence the relation F is shift-invariant.

The image of F under the projection (y, z) → z is dense. To see this, consider any finite word w and a configuration x with x [-|w|,0) = w. The pair (x, 0) represents some (y, z) ∈ F , and because z = χ 0+ (x) we have z [-|w|,0) = w. The denseness follows now from shift invariance and the fact that w was arbitrary. The image of F under the projection is closed so the image is the whole S Z .

The proof for the other projection is analogous.

Corollary 9. If F ⊂ S Z × S Z defined by a bijective block rule χ is a function (that is, if for all y ∈ S Z there is at most one z ∈ S Z such that (y, z) ∈ F ) then this function f : y → z is a surjective cellular automaton.
Proof. Because the projections (y, z) → y and (y, z) → z are onto, the function f is full and surjective. Because the relation F ⊂ S Z × S Z is closed, the function f is continuous. As it is continuous and shift-invariant, it is a cellular automaton.

Definition 10. Let χ be a bijective block rule such that the slider relation it defines is a function f : S Z -→ S Z . The surjective cellular automaton f is called the slider defined by χ.

Example 3 indicates that the slider for the block rule swapping two states is the left shift. By Corollary 9 every slider is a surjective CA. But not every surjective CA is a slider. This will follow from an exact characterization of which cellular automata are sliders below.

Characterization of sliders

We start by improving Corollary 9, by showing that sliders are left-closing cellular automata.

Definition 11. Two configurations y and y are right-asymptotic if there is an

index i ∈ Z such that y [i,∞) = y [i,∞) . They are called left-asymptotic if there is an index i ∈ Z such that y (-∞,i) = y (-∞,i) . A CA f is left-closing if for
any two different right-asymptotic configurations y and y we have f (y) = f (y ). Right-closing CA are defined symmetrically using left-asymptotic configurations.

Lemma 12. A slider is a left-closing cellular automaton.

Proof. Let slider f be defined by a bijective block rule χ : S m → S m , so that f is a surjective cellular automaton. Let ξ be the inverse of χ.

Suppose f is not left-closing, so that there exist two distinct right-asymptotic configurations y and y such that f (y) = f (y ). We may suppose the rightmost difference in y and y is at the origin. Let r be a radius for the local rule of f , where we may suppose r ≥ m, and let y [-2r,2r] = w 0 v, y [-2r,2r] = w 1 v where |w 1 | = |w 2 | = 2r + 1. We can apply the local rule of f to words, shrinking them by r symbols on each side, and write F : S * → S * for this map. Since y and y have the same f -image, we have F (w 0 v) = F (w 1 v).

Let n be such that 2 n > |S| m and for each k ∈ {0, 1} n , define the configuration

y k = ...0000w k1 vw k2 v • • • vw kn v.0000...
where the right tail of 0s begins at the origin. For each y k , pick a point x k representing (y k , f (y k )) at the origin. By the pigeon hole principle, there exist

k = k such that (x k ) [0,m) = (x k ) [0,m) .
Let j be the maximal coordinate where k and k differ. Now, the rightmost difference in y k and y k is in coordinate R = -2r -1 -(4r + 1)(n -j) (the last coordinate of the word w kj ). We have r,∞) by the assumption that j is the rightmost coordinate where k and k differ, and by

f (y k ) [R-r,∞) = f (y k ) [R-
F (w 0 v) = F (w 1 v). Thus we also have (x k ) [R-r,0) = (x k ) [R-r,0) , since χ 0+ (x k ) = f (y k ) and χ 0+ (x k ) = f (y k ) and these sweeps do not modify coordinates in [R -r, 0). Recall that we have (x k ) [0,m) = (x k ) [0,m) by the choice of k and k , so (x k ) [R-r,m) and (x k ) [R-r,m) . Now, we should have ξ 0-(x k ) = y k and ξ 0-(x k ) = y k , in particular we should have ξ 0-(x k ) R = ξ 0-(x k ) R . But this is impossible: ξ 0-(x k ) R is com- pletely determined by (x k ) [R-m+1,m) and similarly ξ 0-(x k ) R is determined by (x k ) [R-m+1,m) , but (x k ) [R-m+1,m) = (x k ) [R-m+1,m) since (x k ) [R-r,m) = (x k ) [R-r,m) and r ≥ m.
In the rest of this section, we only consider the case when the slider relation F that χ defines is a function.

Next we analyze numbers of representations. We call a representation (x, i) of a pair (y, z) simply a representation of configuration y, because z = f (y) is determined by y. Let R(y, i) be the set of configurations x such that (x, i) is a representation of y. By Lemma 6 the elements of R(y, i) have the form ) for some word w ∈ S n where n is the block length of χ.

x = f (y) (-∞,i) • w • y [i+n,∞
By Lemma 7 the cardinality of the set R(y, i) is independent of i. Let us denote by N (y) this cardinality. It turns out that the number is also independent of the configuration y.

Lemma 13. N (y) = N (y ) for all configurations y, y .

Proof. Let n be the block length of rule χ.

(i) Assume first that y, y are left-asymptotic. There is an index i ∈ Z such that y (-∞,i) = y (-∞,i) . Then for any z we have that z

(-∞,i) y [i,∞) ∈ R(y, i -n) if and only if z (-∞,i) y [i,∞) ∈ R(y , i -n). This gives a bijection between R(y, i -n) and R(y , i -n) so that N (y) = |R(y, i -n)| = |R(y , i -n)| = N (y )
. (ii) Assume then that y, y are right-asymptotic. Also f (y) and f (y ) are rightasymptotic so there is ) we have that χ i+ (x ) = f (y ). The configuration y represented by (x , i) is right-asymptotic with y and satisfies f (y ) = f (y ). Because f is left-closing by Lemma 12, we must have y = y . We conclude that f (y As N (y) is independent of y we write N for short.

an index i ∈ Z such that f (y) [i,∞) = f (y ) [i,∞) . Consider z [i,∞) be such that x = f (y) (-∞,i) z [i,∞) ∈ R(y, i). Then χ i+ (x) = f (y). Consider then x = f (y ) (-∞,i) z [i,∞) obtained by replacing the left half f (y) (-∞,i) by f (y ) (-∞,i) . Because f (y) [i,∞) = f (y ) [i,∞
) (-∞,i) z [i,∞) ∈ R(y, i) implies that f (y ) (-∞,i) z [i,∞) ∈ R(y , i),
Next we define right stairs. They were defined in [START_REF] Kari | Representation of reversible cellular automata with block permutations[END_REF] for reversible cellular automata -here we generalize the concept to other CA and show that the concept behaves well when the cellular automaton is left-closing. A right stair is a pair of words that can be extracted from two consecutive configurations x and f (x) that coincide with y and z, respectively, as shown in Figure 2. The precise definition is as follows.

Definition 14. Let f : S Z -→ S Z be a cellular automaton, and let m be a positive integer. Let y ∈ S [i+3m,∞) be a right infinite word and let z ∈ S (-∞,i) be a left-infinite word. -A pair of words (v, w) ∈ S 2m × S 2m is a right stair connecting (y, z) if there is a configuration x ∈ S Z such that vy = x [i+m,∞) and zw = f (x) (-∞,i+2m) . -The stair has length 3m and it is confirmed (at position i) by configuration

x. -We write Ψ 3m (y, z) for the set of all right stairs of length 3m connecting (y, z). -We write Ψ 3m for the union of Ψ 3m (y, z) over all y and z.

Due to shift invariance, x confirms (v, w) ∈ Ψ 3m (y, z) if and only if σ(x) confirms (v, w) ∈ Ψ 3m (σ(y), σ(z)). This means that Ψ 3m (y, z) = Ψ 3m (σ(y), σ(z)), so it is enough to consider i = 0 in Definition 14. In terms of cylinders, (v, w) We need the following known fact concerning left-closing CA. It appears as Proposition 5.44 in [START_REF] Kůrka | Topological dynamics of cellular automata[END_REF] where it is stated for right-closing CA. See Figure 3(a) for an illustration.

∈ Ψ 3m if and only if f ([v] [m,3m) ) ∩ [w] [0,2m) = ∅.
Lemma 15 (Proposition 5.44 in [START_REF] Kůrka | Topological dynamics of cellular automata[END_REF]). Let f be a left-closing CA. For all sufficiently large m ∈ N, if s ∈ S m and t ∈ S 2m are such that f

([s] (m,2m] )∩[t] (0,2m] = ∅ then for all b ∈ S there exists a unique a ∈ S such that f ([as] [m,2m] ) ∩ [bt] [0,2m] = ∅.
The condition f ([s] (m,2m] ) ∩ [t] (0,2m] = ∅ is just a way to write that there exists x ∈ S Z with x (m,2m] = s and f (x) (0,2m] = t. Note that the statement of the lemma has two parts: the existence of a and the uniqueness of a. We need both parts in the following.

A number m is a strong3 left-closing radius for a CA f if it satisfies the claim of Lemma 15, and furthermore m ≥ 2r where r ≥ 1 is a neighborhood radius of f . Next we state corollaries of the previous lemma, phrased for right stairs in place of s and t to be directly applicable in our setup. Proof. (a) Let y, y ∈ S [3m,∞) and z, z ∈ S (-∞,0) be arbitrary. It is enough to prove that Ψ 3m (y , z ) ⊆ Ψ 3m (y, z). The claim then follows from this and shift invariance Ψ 3m (y, z) = Ψ 3m (σ(y), σ(z)).

First we show that Ψ 3m (y , z ) ⊆ Ψ 3m (y, z ). Let (v, w) ∈ Ψ 3m (y , z ) be arbitrary, so that there exists

x ∈ [vy ] [m,∞) such that f (x ) (-∞,2m) = z w. Then (v, w) ∈ Ψ 3m (y, z ) is confirmed by the configuration x such that x (-∞,3m) = x (-∞,3m) and x [3m,∞) = y. Indeed, x [m,∞) =
vy, and because m ≥ r, the radius of the local rule of f , we also have f

(x ) (-∞,2m) = f (x ) (-∞,2m) = z w.
Next we show that Ψ 3m (y, z ) ⊆ Ψ 3m (y, z). Let (v, w) ∈ Ψ 3m (y, z ). We start with finite extensions of w on the left: we prove that for every finite word u ∈ S * we have f ([vy] [m,∞) )∩[uw] [-|u|,2m) = ∅. Suppose the contrary, and let bu ∈ S k+1 be the shortest counter example, with b ∈ S and u ∈ S k . (By the assumptions, the empty word is not a counter example.) By the minimality of bu, there exists

x r ∈ [vy] [m,∞) such that f (x r ) [-k,2m) = uw. Choose s = x r
[-k+m,-k+2m) and t = f (x r ) [-k,-k+2m) and apply the existence part of Lemma 15. By the lemma, there exists a configuration

x l such that x l [-k+m,-k+2m) = x r [-k+m,-k+2m) and f (x l ) [-k-1,-k+2m) = b • f (x r ) [-k,-k+2m) .
Consider x obtained by gluing together the left half of x l and the right half of x r : define x (-∞,-k+2m) = x l (-∞,-k+2m) and x [-k+m,∞) = x r [-k+m,∞) . Note that in the region [-k + m, -k + 2m) configurations x l and x r have the same value. By applying the local rule of f with radius r we also get that f

(x) (-k-1,-k+2m-r) = f (x l ) (-k-1,-k+2m-r) = b • f (x r ) [-k,-k+2m-r) and f (x) [-k+m+r,2m) = f (x r ) [-k+m+r,2m) . Because m ≥ 2r we have -k + 2m -r ≥ -k + m + r, so that f (x) (-k-1,2m) = b • f (x r ) (-k,2m) = buw. We also have x [m,∞) = x r
[m,∞) = vy, so that x proves that bu is not a counter example. Consider then the infinite extension of w on the left by z: Applying the finite case above to each finite suffix of z and by taking a limit, we see with a simple compactness argument that there exists

x ∈ [vy] [m,∞) such that f (x) [-∞,2m) = zw. This proves that (v, w) ∈ Ψ 3m (y, z).
(b) Let (vc, wd) ∈ Ψ 3m and let b ∈ S be arbitrary. Let y ∈ S [3m,∞) be arbitrary, and and let z ∈ S (-∞,0) be such that z -1 = b. By (a) we have that (vc, wd) ∈ Ψ 3m (y, z). Let x be a configuration that confirms this, so

x [m,∞) = vcy and f (x) (-∞,2m) = zwd. Let a = x m-1 . Because x [m-1,3m-1) = av and f (x) [-1,2m-1) = bw, configuration x confirms (at position i = -1) that (av, bw) ∈ Ψ 3m .
Let us prove that a is unique. Suppose that also (a v, bw) ∈ Ψ 3m . We apply the uniqueness part of Lemma 15 on s and t where t = wd and s is the prefix of v of length m.

Because (a v, bw) is a right stair, f ([a v] [m-1,3m-1) ) ∩ [bw] [-1,2m-1) = ∅. Because m -1 ≥ 2r -1 ≥ r, the local rule of f assigns f (x) 2m-1 = d for all x ∈ [a v] [m-1,3m-1) , so that f ([a v] [m-1,3m-1) ) ∩ [bwd] [-1,2m) = ∅. But then f ([a s] [m-1,2m) ) ∩ [bt] [-1,2m) = ∅,
so that by Lemma 15 we must have a = a. a ,b,c,d ∈ S and v, w ∈ S 2m-1 from x and x as follows: avc = x [k,k+2m] and

(c) Suppose x = x both confirm that (v , w ) ∈ Ψ 3m (y, z). Then x [m,∞) = v y = x [m,∞) . Let k < m be the largest index such that x k = x k . Extract a,
a vc = x [k,k+2m] and bwd = f (x) [k-m,k+m] = f (x ) [k-m,k+m]
. Then (vc, wd) ∈ Ψ 3m and (av, bw), (a v, bw) ∈ Ψ 3m . This contradicts (b).

Now we can state another constraint on sliders.

Lemma 17. Let f be a slider. Let m be a strong left-closing radius, and big enough so that f is defined by a bijective block rule χ : S n -→ S n of block length n = 3m. Let N be the number of representatives of configurations (independent of the configuration) with respect to χ. Then

N • |Ψ n | = |S| n . In particular, |Ψ n | divides |S| n . Proof. Fix any y ∈ S [3m,∞) and z ∈ S (-∞,0) . Denote A = {x ∈ S Z | x [3m,∞) = y and f (x) (-∞,0) = z}. Consider the function A -→ Ψ 3m (y, z) defined by x → (x [m,3m) , f (x) [0,2m) ).
It is surjective by the definition of Ψ 3m (y, z), and it is injective by Corollary 16(c). Because Ψ 3m (y, z) = Ψ 3m by Corollary 16(a), we see that |A| = |Ψ 3m |.

For each w ∈ S 3m define configuration x w = zwy. Representations (x, 0) of y ∈ A are precisely (x w , 0) for w ∈ S 3m . Because each y has N representations and there are |S| 3m words w we obtain that N • |Ψ 3m | = |S| 3m . Now we state the converse: the constraints we have for sliders are sufficient. This completes the characterization of sliders. Let us define a block rule χ : S n+1 -→ S n+1 as follows (see Figure 3).Consider any c ∈ S, any k ∈ {1, 2, . . . , N } and any (av, bw) ∈ Ψ n where a, b ∈ S and v, w ∈ S 2m-1 . Let d = f loc (avc). We set χ : π((av, bw), k) • c → b • π((vc, wd), k)). This completely defines χ, but to see that it is well defined we next show that (vc, wd) is a right stair. By Corollary 16(a) we have that (av, bw) ∈ Ψ n (cy, z) for arbitrary y, z so there is a configuration x such that x [m,∞) = avcy and f (x) (∞,2m) = zbw. The local rule f loc determines that f (x) 2m = f loc (avc) = d. It follows that (vc, wd) ∈ Ψ n (y, zb), confirmed by x at position i = 1. Now that we know that χ is well defined, let us prove that χ is a bijection. Suppose π((av, bw), k) As χ is a bijective block rule, it defines a slider relation F . We need to prove that for every configuration y, the only z such that (y, z) ∈ F is z = f (y). Therefore, consider an arbitrary representation (x, i) of (y, z)

• c and π((a v , b w ), k ) • c have the same image b • π((vc, wd), k)) = b • π((v c , w d ), k )).
∈ F . Write x = z (-∞,i) • π((av, bw), k) • c • y [i+n+1,∞) for letters a, c, b ∈ S words v, w ∈ S 2m-1
and k ∈ {1, 2, . . . , N }. This can be done and as π is surjective and all items in this representation are unique as π is injective. We have (av, bw) ∈ Ψ n (cy, z) so by Corollary 16(c) there is a unique configuration x that confirms this. Then

x [i+m,∞) = avc • y [i+n+1,∞) and f (x ) (-∞,i+2m) = z (-∞,i) • bw. Associate x to (x, i) by defining g(x, i) = x .
Let us show that g(χ i (x), i + 1) = g(x, i). By the definition of χ we have

χ i (x) = z (-∞,i) • b • π((vc, wd), k)) • y [i+n+1,∞)
where d = f loc (avc). To prove that g(χ i (x), i + 1) = x = g(x, i) it is enough to show that x confirms (vc, wd) ∈ Ψ n (y, zb). But this is the case because

x [i+m+1,∞) = vc • y [i+n+1,∞) and f (x ) (-∞,i+2m+1) = z (-∞,i) • bwd. The fact that f (x ) i+2m = d follows from x [i+m,i+3m] = avc and d = f loc (avc).
By induction we have that for any j ≥ i holds g(χ [i,j) (x), j) = x . Moreover, pair (χ [i,j) (x), j) represents the same (y, z) ∈ F as (x, i). Therefore, x [j+n+1,∞) = y [j+n+1,∞) and f (x ) (-∞,j) = z (-∞,j) for all j ≥ i. Let us look into position p = i + n + m + 1. Using any j > p we get f (x ) p = z p and using j = i we get x [p-m,p+m] = y [p-m,p+m] . This means that z p = f loc (y [p-m,p+m] ), that is, z p = f (y) p . Because i was arbitrary, p is arbitrary. We have that z = f (y), which completes the proof. By Corollary 16, for a left-closing cellular automaton f the limit

λ f = lim m→∞ |Ψ 3m | |S| 3m (2)
is reached in finite time, namely as soon as m is a left-closing radius, and thus λ f is rational for left-closing f . In [START_REF] Kari | Representation of reversible cellular automata with block permutations[END_REF] it is shown that the map f → λ f gives a homomorphism from the group of reversible cellular automata into the rational

χ [i,k-1] (x) k = [ 1 a ],
meaning that the sweep is synchronized (in the sense that whatever information was coming from the left is forgotten and the sweep continues the same way) and χ i+ (x) n is determined by x [k,n] for all i < k. Thus, in this case χ i+ (x) n converges.

Suppose then that for all k < n, x k = [ 0 a ] for some a ∈ {0, 1}. If

x k = [ 0 0 ] for some k < n, then since x k-1 = [ 1 0 ] we also have χ [i,k-2] (x) k-1 = [ 1 0
]. Thus, the value at k does not change when χ is applied at k -1, and as in the previous paragraph, the sweep is synchronized at this position. Again χ i+ (x) n is determined by x [k,n] for all i < k, so χ i+ (x) n converges.

In the remaining case,

x k = [ 0 1 ] for all k < n. Then since χ([ 0 1 ] [ 0 1 ]) = [ 0 1 ] [ 0 1
], the rule is not applied in the left tail of x, and thus certainly χ i+ (x) n converges.

The function defined by the sweeper relation is not continuous at

[ 0 1 ] Z since χ Z ([ 0 1 ] Z ) = [ 0 1 ]
Z while for any n ∈ N we have Note that in L n , there are n sweeps (slider applications) in total, and the last sweep goes from right to left. We have In Theorem 30 below we will show a close relation between this "slider hierarchy" and a "closingness hierarchy" defined as follows, exactly analogously. Let L cl denote the set of left-closing CA and R cl the set of right-closing CA. Define

χ Z (... [ 0 0 ] [ 0 0 ] [ 0 0 ] [ 0 1 ] n . [ 0 1 ] N ) = ... [ 0 0 ] [ 0 0 ] [ 1 0 ] [ 1 0 ] n . [ 1 0 ] N 3
L 1 = L, R 1 = R, ∆ 1 = ∆. See Figure 4. ∆1 L1 ∆2 R1 L2 ∆3 R2 L3 ∆4 R3 L4 ∆5 R4 • • • • • •
L cl 0 = R cl 0 = {id} and for all k, L cl k+1 = L cl • R cl k and R cl k+1 = R cl • L cl k .
As always with such hierarchies, it is natural to ask whether they are infinite or collapse at some finite level. We do not know if either hierarchy collapses, but we show that after the first level, the hierarchies coincide. The main ingredients for the theorem are the following two lemmata.

Lemma 28. Let f be a left-closing CA. For all n large enough, |Ψ n | divides some power of |S|.

Lemma 29. Let f be a left-closing CA. Then for any large enough n, we have

σ n • f ∈ R. Theorem 30. For each k ∈ N with k ≥ 2 we have L k = R cl k and R k = L cl k .
A cellular automaton f is bi-closing if it is both left-closing and right-closing, i.e. f ∈ ∆ cl

Decidability

In this section, we show that our characterization of sliders and sweepers shows that the existence of them for a given CA is decidable. We also show that given a block rule, whether it defines some CA as a slider (equivalently as a sweeper) is decidable. We have seen that sweepers can also define shift-commuting functions which are not continuous. We show that this condition is also decidable.

Lemma 32. Given a cellular automaton f : S Z → S Z , it is decidable whether it is left-closing, and when f is left-closing, a strong left-closing radius can be effectively computed.

Lemma 33. Given a left-closing cellular automaton f : S Z → S Z , one can effectively compute the rational number λ f defined in Equation (2) on page 11.

Theorem 34. Given a cellular automaton f : S Z → S Z , it is decidable whether f is a slider (resp. sweeper).

We now move on to showing that given a block rule, we can check whether its slider or sweeper relation defines a CA.

In the rest of this section, we explain the automata-theoretic nature of both types of rules, which allows one to decide many properties of the slider and sweeper relations even when they do not define cellular automata. As is a common convention in automata theory, all claims in the rest of this section have constructive proofs (and thus imply decidability results), unless otherwise specified.

We recall definitions from [START_REF] Perrin | Infinite words: automata, semigroups, logic and games[END_REF] for automata on bi-infinite words. A finite-state automaton is A = (Q, S, E, I, F ) where Q is a finite set of states, S the alphabet, E ⊂ Q × S × Q the transition relation, I ⊂ Q the set of initial states and F ⊂ Q the set of final states.

The pair (Q, E) can be naturally seen as a labeled graph with labels in S. The language of such an automaton A the set L(A) ⊂ S Z of labels of bi-infinite paths in (Q, E) such that some state in I is visited infinitely many times to the left (negative indices) and some state in F infinitely many times to the right. Languages of finite-state automata are called recognizable.

In the theorems of this section, note that the set S Z × S Z is in a natural bijection with (S 2 ) Z .

Proposition 35. Let χ : S m → S m be a bijective block rule. Then the corresponding slider relation F ⊂ (S 2 ) Z is recognizable.

Lemma 36. Given a recognizable set X ⊂ (S 2 ) Z , interpreted as a binary relation over S Z , it is decidable whether X defines a function.

The following is a direct corollary.

Theorem 37. Given a block rule, it is decidable whether it is the sliding rule of a CA.

We now discuss sweeping rules.

Proposition 38. Let χ : S m → S m be a block rule. Then the corresponding sweeper relation F ⊂ (S 2 ) Z is recognizable.

The sweeping relation need not be closed, as shown in Example 26. However, whether it is closed is decidable.

Lemma 39. Given a recognizable X ⊂ S Z , it is decidable whether X is closed.

Theorem 40. Given a block rule, it is decidable whether the sweeping relation it defines is a CA.

Future work and open problems

To obtain a practical computer implementation method for cellular automata, one would need much more work. The radius of χ should be given precise bounds, and we would also need bounds on how long it takes until the sweep starts producing correct values. Future work will involve clarifying the connection between the radii m of local rules χ : S m → S m and the strong left-closing radii, the study of non-bijective local rules, and the study of sweeping rules on periodic configurations.

On the side of theory, it was shown in Section 3 that the hierarchy of left-and right-closing cellular automata corresponds to the hierarchy of sweeps starting from the second level. Neither hierarchy collapses on the first level, since there exists CA which are left-closing but not right-closing, from which one also obtains CA which are in L 1 but not R 1 .

Question 41. Does the hierarchy collapse on a finite level? Is every surjective CA in this hierarchy? As we do not know which cellular automata appear on which levels, we do not know whether these levels are decidable. For example we do not know whether it is decidable if a given CA is the composition of a left sweep and a right sweep.

It seems likely that the theory of sliders can be extended to shifts of finite type. If X is a subshift, say that a homeomorphism χ : X → X is local if its application modifies only a (uniformly) bounded set of coordinates. One can define sliding applications of such homeomorphisms exactly as in the case of S Z . Question 42. Let X ⊂ S Z be a transitive subshift of finite type. Which endomorphisms of X are defined by a sliding rule defined by a local homeomorphism?

In [START_REF] Kari | Representation of reversible cellular automata with block permutations[END_REF], block representations are obtained for cellular automata in one and two dimensions, by considering the set of stairs of reversible cellular automata. Since stairs play a fundamental role for sliders as well, it seems natural to attempt to generalize our theory to higher dimensions.

  and the converse implication also holds by a symmetric argument. As in (i), we get that N (y) = |R(y, i)| = |R(y , i)| = N (y ). (iii) Let y, y be arbitrary. Configuration y = y (-∞,0) y [0,∞) is left-asymptotic with y and right-asymptotic with y . By cases (i) and (ii) above we have N (y) = N (y ) = N (y ).

Fig. 2 .

 2 Fig. 2. A right stair (v, w) of length 3m connecting y and z, confirmed by x at position i = 0.

Fig. 3 .

 3 Fig. 3. (a) An illustration for Lemma 15, and (b) an illustration for Corollary 16(b) and for Lemma 18.

Corollary 16 .

 16 Let f be a left-closing CA. Let m be a strong left-closing radius. (a) Ψ 3m (y, z) = Ψ 3m for all y and z. (b) Let (vc, wd) ∈ Ψ 3m for c, d ∈ S and v, w ∈ S 2m-1 . For every b ∈ S there exists a unique a ∈ S such that (av, bw) ∈ Ψ 3m . (See Figure 3(b) for an illustration.) (c) Every (v, w) ∈ Ψ 3m (y, z) is confirmed by a unique x.

Lemma 18 .

 18 Let f be a left-closing cellular automaton, let m be a strong leftclosing radius, and assume that |Ψ n | divides |S| n for n = 3m. Then f is a slider. Proof. Let N = |S| n /|Ψ n | and pick an arbitrary bijection π : Ψ n ×{1, 2, . . . , N } -→ S n . Let f loc : S 2m+1 -→ S be the local rule of radius m for the cellular automaton f .

  We clearly have b = b , and because π is a bijection, we have v = v , c = c , w = w , d = d and k = k . By Corollary 16(a) we also have that a = a .

  Realization of bi-closing CA using LR and RL slidersIn the definition of a slider we use a left-to-right slide of the window to realize the CA transition. Of course, one can analogously define right-to-left sliders and state a characterization via right-closing CA. We can also alternate these two types of rules, and obtain a ladder-shaped hierarchy analogous to the Borel, arithmetic and polynomial hierarchies. Definition 27. Let R denote the set of CA definable as slider relations with the "left to right" definition as in Definition 10. Analogously let L denote the set of CA definable as right-to-left slider relations. Denote ∆ = L ∩ R. Let now L 0 = R 0 = {id}, and for all k ∈ N 0 let L k+1 = L • R k and R k+1 = R • L k . For all n, write ∆ n = L n ∩ R n .

Fig. 4 .

 4 Fig. 4. The sliding hierarchy.

1 .

 1 Such cellular automata are also called open, since they map open sets to open sets. By the previous result, every bi-closing CA can be realized by a left-to-right sweep followed by a right-to-left sweep by bijective block rules: Theorem 31. Each bi-closing CA is in ∆ 2 .

The word 'strong' is added to distinguish this from the weaker closing radius obtained directly from the definition by a compactness argument.

Acknowledgement. The authors gratefully acknowledge partial support for this work by two short term scientific missions of the EU COST Action IC1405.

Research supported by the Academy of Finland grant 296018.

numbers under multiplication. For a prime number p and an integer n, write v p (n) for the largest exponent k such that p k |n. For prime p and rational r = m/n, write v p (r) = v p (m) -v p (n) for the p-adic valuation of r.

Theorem 19. The function f is a slider if and only if f is a left-closing cellular automaton and v p (λ f ) ≤ 0 for all primes p.

Example 20. Let A = {0, 1} × {0, 1, 2} and write σ 2 and σ 3 for the left shifts on the two tracks of A Z . Then consider f = σ 2 × σ -1 3 . For this CA we have by a direct computation

and thus f is not a slider. Similarly we see that

2 is not a slider.

Example 21. Let S = {0, 1} and consider the exclusive-or CA with neighborhood

Definition of sweepers

An alternative approach not requiring bijectivity of χ is specified in the following:

Lemma 23. The projection (y, z) → y on the first component maps a sweeper relation F surjectively onto S Z . The relation F is a function f if and only if for each configuration y the limit lim i→-∞ χ i+ (y) exists and equals f (y).

Definition 24. Let χ be a block rule such that for each configuration y the limit z = lim i→-∞ χ i+ (y) exists. The function y → z is called the sweeper defined by χ.

Compared to definition 10 the advantage of definition 24 is that it does not require χ to be bijective. But as long as χ is bijective, there is in fact no difference.

Theorem 25. Let χ be a bijective block rule and f a one-dimensional CA. The slider relation defined by χ is equal to f if and only if the sweeper relation it defines is equal to f . While the slider and sweeper relations defined by a block rule are equal when at least one of them defines a cellular automaton, sweeper relations can also define non-continuous functions.

We claim that lim i→-∞ χ i+ (x) is well-defined for all x ∈ S Z , so that the sweeper relation χ defines is a function. Let x ∈ S Z be arbitrary, and let n ∈ Z. We need to show that χ i+ (x) n converges.

Suppose first that for some k < n, we have x k = [ 1 a ] for a ∈ {0, 1}. Then for all i < k, the value χ i+ (x) n is independent of the values x j ≤ k, since