Ville Salo
email: vsalo@dim.uchile.cl

Ilkka Törmä

Group-Walking Automata

Keywords: group-walking automaton, torsion group, periodic group, multiheaded automaton, subshift

In the setting of symbolic dynamics on discrete finitely generated infinite groups, we define a model of multi-headed finite automata that walk on Cayley graphs, and use it to define subshifts. We characterize the torsion groups (also known as periodic groups) as those on which the group-walking automata are strictly weaker than Turing machines.

Introduction

One of the central objects in symbolic dynamics is the dynamical system S G (where G is a discrete group and S a finite alphabet), called the full shift, where G acts by translations. In particular, one studies its subsystems, usually called subshifts, and classes of such subsystems. Some of the important classes studied are the SFTs (subshifts defined by a finite set of forbidden patterns), sofic shifts (the factors of SFTs) and the effective, or Π 0 1 subshifts (defined by a recursively enumerable set of forbidden patterns). SFTs and sofic shifts are natural objects to study on all groups, and a robust notion of effectiveness of subshifts on arbitrary groups is given in [START_REF] Aubrun | A notion of effectiveness for subshifts on finitely generated groups[END_REF] (see also Section 5).

In this paper, continuing the work in [START_REF] Salo | Plane-walking automata[END_REF], we define some new families of subshifts on an arbitrary (discrete finitely generated infinite) group G. Namely, we discuss the class of subshifts defined by certain multi-headed automata that walk on the Cayley graph of the group G. We have studied the case G = Z d in [START_REF] Salo | Plane-walking automata[END_REF], the main result being that three-headed finite-state automata define the same subshifts as general Turing machines. 3 It turns out that up to notational complications and a few simple tricks, the same result can be shown on all groups containing a copy of Z. We show this in Theorem 1.

Most finitely generated groups of practical interest contain a copy of Z. For example, in addition to infinite (finitely generated) abelian groups, this is true for free groups, Baumslag-Solitar groups, the Heisenberg group, the Thompson groups F , T and V , and the general linear groups GL(n, Z). In fact, infinite finitely generated groups without a copy of Z, known as torsion groups, are quite rare and hard to construct. Nevertheless, many examples exist in the literature. The question is particularly hard in the case that the torsion is bounded, that is, there exists n ∈ N such that every element of the group generates a subgroup of order at most n. See [START_REF] Adian | The burnside problem on periodic groups and related questions[END_REF] for a discussion of groups with bounded torsion. In the case of unbounded torsion, there are examples that are relatively simple to define, and simple to prove torsion. We mention in particular [START_REF] Grigorčuk | On Burnside's problem on periodic groups[END_REF][START_REF] Gupta | On the burnside problem for periodic groups[END_REF].

Given that such groups exist, an obvious question is whether we can extend Theorem 1 to this case. It turns out that we cannot: in Theorem 2 we show that a subshift on a torsion group accepted by a multi-headed automaton 'cannot be too sparse', and as a further result we obtain Theorem 6, which characterizes the torsion groups as those on which multi-headed automata are strictly weaker than Turing machines.

Definitions and examples

Subshifts

In this section, we define some basic notions of of symbolic dynamics and computability. Some references on symbolic dynamics on general groups are [START_REF] Ceccherini-Silberstein | Cellular Automata and Groups[END_REF][START_REF] Aubrun | A notion of effectiveness for subshifts on finitely generated groups[END_REF], and a standard reference on Z is [START_REF] Lind | An introduction to symbolic dynamics and coding[END_REF].

Let G be a group with identity element 1 G ∈ G. Our groups are always infinite (the finite case being trivial) and finitely generated (since the notions we consider are local). For convenience, if G is finitely generated, we fix a symmetric finite set s(G) ⊂ G of generators for it. The set s(G) * consists of all finite words over s(G), and for v, w ∈ s(G) * , we denote v ∼ w and v ∼ g if the words correspond to the same element g ∈ G. We denote by B G (n) the ball of radius n with respect to the fixed set of generators:

B G (n) = {g ∈ G | w ∈ s(G) * , |w| ≤ n, w ∼ g}.
A torsion element of a group G is an element g ∈ G that satisfies g n = 1 G for some n ≥ 1. If all elements of G are torsions, then G is a torsion group. To each torsion element g ∈ G we associate its order t G (g) = min{n ≥ 1 | g n = 1 G }, and to each finitely generated torsion group we associate the torsion function

T G : N → N, defined by T G (n) = max{t G (g) | g ∈ B G (n)}.
A non-torsion group, conversely, is one containing an isomorphic copy of Z.

Both alphabet and state set mean any finite set. The symbol S always means an alphabet, and the set S G is the full G-shift over S. Its elements, usually denoted by x, y, z, are called configurations. We define both a left and a right action of G on S G , called the left and right shifts. The left action is given by (g

• x) h = x g -1 h . It is indeed an action because (g 2 • (g 1 • x)) h = (g 1 • x) g -1 2 h = x g -1 1 g -1 2 h = x (g2g1) -1 h = (g 2 g 1 • x) h . The right action is given by σ R g (x) h = x hg . It is indeed an action because σ R g2 (σ R g1 (x)) h = σ R g1 (x) hg2 = x hg2g1 = σ R g2g1 (x) h .
We give S G the product topology induced by the discrete topology on S, making it a compact metrizable space. It is easy to show that both actions are continuous in this topology. A subshift of S G is a topologically closed subset of S G closed under the left action of G. A cellular automaton on a subshift X ⊂ S G is a continuous map f : X → X that commutes with the left shifts in the sense that g • f (x) = f (g • x) holds for all x ∈ S G and g ∈ G. We denote by Aut(X) the group of bijective cellular automata on X under composition.

For us, the main importance of the left action is that it allows for nice definitions of subshifts and cellular automata. On the other hand, when the right action of an element g ∈ G is well-defined on a subshift, it is a cellular automaton. In particular, the right actions show that Aut(S G ) contains a copy of the group G, by the injective group homomorphism g → σ R Subshifts can be characterized as sets X ⊂ S G for which there exists a set of forbidden patterns F such that

X = {x ∈ S G | ∀P ∈ F : ∀g ∈ G : g • x / ∈ [P ]}.
Each cellular automaton on X has a radius r ∈ N and a local rule

F : S B G (r) → S such that f (x) g = F (g -1 • x| B G (r)
) holds for all x ∈ X and g ∈ G.

Example 1. Let G be the free group generated by g, h ∈ G, and X ⊂ S G the set

{x ∈ S G | ∀g ∈ G : ∀n ∈ Z : x gh n = x g }.
We show that X is a subshift, and for that, let x ∈ X and g ∈ G. We need to show g • x ∈ X. Given f ∈ G and n ∈ Z, we have

(f • x) gh n = x f -1 gh n = x f -1 g = (f • x) g
by the definition of the left action, and the fact x ∈ X.

Definition 1. If S 0 is a finite alphabet, then the one-S subshift on a group G is the subshift X G S ⊂ S G where a finite pattern P ∈ S D is forbidden if and only if there exist d = e ∈ D with P e = 0 = P d . If 0 / ∈ S, we write

X G S = X G S∪{0} .
The group G is usually clear from context, and we write X S for X G S .

Definition 2. Let S 0 be a finite alphabet. A configuration x ∈ S G is k- sparse if it satisfies |{g ∈ G | x g = 0}| ≤ k. A subshift is k-sparse if each of its configurations is k-sparse, and sparse if it is k-sparse for some k ∈ N.
The one-S subshift X S is of course a 1-sparse subshift on any group. Note that in a sparse subshift, there is a global bound on the number of nonzero symbols. The sum x + y of sparse configurations x, y ∈ S G with disjoint support (no g ∈ G satisfies x g = 0 and y g = 0) is defined by

(x + y) g = x g if x g = 0, y g otherwise.
A finite pattern is represented computationally as a finite list of word-symbol pairs (w, d) ∈ s(G) * × S. Such a list is inconsistent if it contains two pairs (v, d) and (w, e) with v ∼ w and d = e (in this case, it does not actually encode a pattern), and otherwise consistent.

Definition 3. The word problem of G is the set E = {w ∈ s(G) * | w ∼ 1 G }
of words that represent the identity element of G. Whether the word problem is decidable is independent of the chosen generator set. We say G is recursively presented if G ∼ = g 1 , . . . , g k | w 1 , w 2 , . . . , where (w i ) i∈N is a computable sequence of relations. 4 This is equivalent to the set E being recursively enumerable.

If G has a decidable word problem, we say that a subshift X ⊂ S G is Π 0 1 if there exists a Turing machine that enumerates a list of consistent forbidden patterns defining it.

A subshift X is Π 0 1 if and only if there exists an oracle Turing machine that, given an oracle for a configuration x ∈ S G (which returns the symbol x w ∈ S for a given word w ∈ s(G) * ), eventually halts if and only if x / ∈ X.

Automata

We now define group-walking automata and the subshifts they recognize. Here and henceforth, by π i we mean the projection to the ith coordinate of a finite Cartesian product.

S G × Y → S G × Y is a CA satisfying π 1 • f = π 1 .
We denote by S(G, k) the class of subshifts X ⊂ S G for which there exists a k-headed automaton A as above such that

X = {x ∈ S G | ∀g, h ∈ G, y ∈ I, n ∈ N : h • π 2 (f n (g • x, y)) / ∈ F }.
We also write S(G) = k≥1 S(G, k).

The intuition for these definitions is the following. A configuration y ∈ Y = k i=1 X Qi consists of k layers π i (y), each of which contains at most one nonzero symbol q i ∈ Q i , representing the i'th head of the automaton in state q i . The cellular automaton f is the update function of the heads: since f has a finite radius, the heads can only move at a bounded speed, and interact over bounded distances. Also, the condition π 1 • f = π 1 ensures that the automaton cannot alter the configuration of S G that it runs on. The clopen sets I, F ⊂ Y are the initial and final states of the automaton. Each of them is a finite union of cylinder sets [P ], and since they are also finite as sets, each of the patterns P necessarily contains all k heads of the automaton. Thus, an initial or finite state specifies the position and internal state for each head, and we translate them by every element of G in the definition of S(G).

The definition is given in dynamical terms to make the connection with cellular automata clearer, and to facilitate the statement and proof of Lemma 3.

With some work, one can show that this model is equivalent to the one we gave in [START_REF] Salo | Plane-walking automata[END_REF] in terms of the classes of subshifts defined.

Example 2. Let G be again the free group generated by the elements g, h ∈ G, and let S = {0, 1}. We define a two-headed group-walking automaton

A = (Q 1 × Q 2 , f, I, F ) on G as follows. The local state sets are Q 1 = {q g , q g -1 } and Q 2 = {q h , q h -1 }, the set of initial states I contains only the cylinder set {x ∈ (Q 1 × Q 2 ) G | x 1 G = (q g , q h )}, and the set of final states F contains the cylinder {x ∈ (Q 1 × Q 2 ) G | x 1 G = (q g -1 , q h -1
)}. This means that the heads of the automaton are initialized at the same coordinate in states q g and q h , and a configuration is rejected if they ever return to the same coordinate in states q g -1 and q h -1 . The CA f moves each head by the step indicated in its state, and if a head encounters a symbol 1 in state q g or q h , it assumes the respective inverse state q g -1 or q h -1 .

In a run of the automaton, the heads start moving in the directions g and h until they encounter symbols 1, and then turn back. If both of them turn at the same time, they will meet again where they started, in the states q g -1 and q h -1 , so the configuration is rejected. If not, the configuration is not rejected. Thus the automaton A defines the subshift X ⊂ S G with the forbidden patterns

{1 G → 0, g → 0, h → 0, . . . , g n-1 → 0, h n-1 → 0, g n → 1, h n → 1} for all n ≥ 1. It is not an SFT.
Naturally, Turing machines are stronger than multi-headed finite automata.

Lemma 1. If G has a decidable word problem and X ∈ S(G), then X ∈ Π 0 1 .

Proof. Let A be a group-walking automaton that defines X. We construct a Turing machine T A that outputs its forbidden patterns. The machine T A enumerates all consistent patterns over G (using the fact that G has a decidable word problem), and simulates a run of the automaton A on each of them, from every initial state. If one of the heads exits the pattern during such a simulation, or every head enters an infinite loop, that simulation is simply discarded. If one of the runs enters a rejecting state on the pattern P before exiting it (from any initial configuration and initial position on the domain D(P )), the machine T A outputs the pattern P . It is clear that T A defines the same subshift as A.

3 Non-torsion groups with a decidable word problem

On non-torsion groups, there are essentially no restrictions on the types of computation a multi-headed finite state automaton can do, apart from the inherent limits of computation. In fact, we will implement all Π 0 1 -subshifts on such groups, using just three heads. The construction is similar to that in [START_REF] Delorme | Pebble automata. figures families recognition and universality[END_REF] and [START_REF] Salo | Plane-walking automata[END_REF]. Theorem 1. If G is finitely generated, infinite and non-torsion, and has a decidable word problem, then S(G, 3) is exactly the class of Π 0 1 -subshifts.

Proof. By Lemma 1, all S(G, 3)-subshifts are Π 0 1 . To show that S(G, 3) contains all Π 0 1 -subshifts, we repeat the proof of Theorem 5 in [START_REF] Salo | Plane-walking automata[END_REF], where the same problem was considered for G = Z d , with one additional detail in the non-abelian case. Since there are not many changes, we refer to [START_REF] Salo | Plane-walking automata[END_REF] for some of the details.

Let X ⊂ S G be a Π 0 1 -subshift, and let h ∈ G be an element of infinite order. Given a Turing machine T enumerating a list of forbidden patterns for X, we construct an automaton A T with three heads, the pointer head, the zig-zag head and the counter head. The relative positions of these heads store a number, which we increment, decrement, multiply and divide by suitable constants, and test for equivalence and divisibility by constants, in order to perform arbitrary computation: such a model is Turing-complete by the results of [START_REF] Schroeppel | A two counter machine cannot calculate 2 N[END_REF].

More precisely, all heads are initialized on the same element of G, which we may assume to be 1 G . The run of the automaton proceeds in sweeps, each of which either corresponds to an arithmetical operation as described above, or moves the heads in some direction. Between these sweeps, the location of both the pointer head and the zig-zag head is some g ∈ G, and the position of the counter head is gh p . The number p ∈ N is the counter value. Changes in the counter value are used to perform computation, and changes to the value g allow us to read the contents of every cell in the configuration.

The operations are implemented as in the case G = Z d (for example, see Proposition 3 in [START_REF] Salo | Plane-walking automata[END_REF]). The only operations that are nontrivial to implement are multiplication and division, and they are dealt with by standard signaling techniques. The details of this are omitted in [START_REF] Salo | Plane-walking automata[END_REF], so we outline the construction here: we explain how to multiply the counter value by a rational number 0 < m n < 1 assuming the counter value is divisible by n; to multiply by a rational number greater than 1, one essentially performs the same steps in reverse.

For this, let g ∈ G be the position of the pointer head. The idea is that the zig-zag head moves to the counter head, which is at gh p , along the progression g, gh, gh 2 , . . .. The two heads then perform a coordinated move along the path g, gh, gh 2 , . . . , gh c , so that they meet exactly at gh m n p . The zig-zag head then returns to the pointer head, and computation continues. We have much freedom in performing these moves, but we fix a particular scheme that works: After the zig-zag head and the counter head meet, the counter head starts moving in steps of h towards the pointer head (so that from the cell gh j , it moves to the cell gh j-1 in one step), until it meets the zig-zag head again. The zig-zag head moves towards the pointer head by h n every step, until it meets the pointer head. Note that n divides p, so that the zig-zag head indeed reaches exactly the cell g. After this, the zig-zag head starts moving back towards the counter head at speed m n-m-1 . More precisely, the zig-zag head carries a modular counter, starting at 0, and at each step it increments this counter. When the modular counter reaches n -m -1, the zig-zag head resets it to 0 and moves by h m . When the zig-zag head reaches the counter head, it turns back, and returns to the pointer head. It is a simple calculation to check that the heads meet exactly at gh m n p , as required, so the counter value has been changed correctly. Now that we can do arbitrary computation in the counter value, we give the algorithm we simulate in it. The algorithm is the same as in the proof of Theorem 5 of in [START_REF] Salo | Plane-walking automata[END_REF], and we reproduce it in Algorithm 1 with trivial modifications. In the algorithm, objects related to the group are stored as they are output by the Turing machine: group elements are finite words over s(G), and patterns P ∈ S D are lists of pairs (w, s) ∈ s(G) * × S meaning P w = s. We assume the Turing machine T outputs an infinite list of forbidden patterns, and enters the state q out every time it outputs a new pattern.

Algorithm 1 The algorithm that the three-headed automaton A T simulates.

1: c ← c0 A configuration of T , set to the initial configuration 2: u ← 1G ∈ G
The position of the pointer head relative to the initial position 3: P : ∅ → S

A finite pattern at the initial position 4: loop 5: repeat 6:

c ← NextConfT (c) Simulate one step of T 7:

until State(c) = qout T outputs something 8:

P ← OutputOf(c) A forbidden pattern 9:

while D(P ) ⊂ D(P ) do 10:

w ← LexMin(D(P ) \ D(P ))

The lexicographically minimal element 11:

for a = u -1 1 , u The function ReadSymbol gives the symbol currently under the pointer head. The procedure MoveBy(a) causes the three heads to assume new positions: if the pointer head and zig-zag head are at g and the counter head is at gh p , they are moved to ga and gah p , respectively. This step is the main difference between the abelian and non-abelian cases, and we explain it below. We note that there are only finitely many different messages sent between the abstract computation and A T , namely the exchange related to ReadSymbol and the commands MoveBy(a) for finitely many a ∈ G. This information exchange can easily be performed by storing the state of the Turing machine T directly in the finite state of the pointer head.

It is easy to see that this algorithm does what we want: whenever the Turing machine T enumerates a forbidden pattern P , we expand the stored pattern P by reading the configuration until its domain contains that of P . If P occurs in the configuration, it is eventually found by the algorithm from some starting position, and conversely, if the automaton halts, this is because it found a forbidden pattern.

To finish the proof, we explain how to perform MoveBy(a). If G is abelian, this can be done as in [START_REF] Salo | Plane-walking automata[END_REF]: the zig-zag head moves to the counter head, informs it of the element of G by which it should move, and returns back. The counter head moves as instructed, and the pointer head does so as well. If the pointer head was previously at g and the counter head at gh P , and both move by a ∈ G, then after this sequence of moves, the pointer head will be at ga, and the counter head at gh p a = gah p , as required. More generally, this works if h is in the center of G. Otherwise, we may have gh p a = gah p . Since we do not necessarily have gah p ∈ g h a, the counter head may not even encode a valid counter value.

However, using the same trick we used to perform multiplications, we can perform the movement in general. First, the zig-zag head moves to the counter head. Then, both heads start moving toward the pointer head. The counter head moves in steps of h -1 , computing the parity of p on the way, and the zig-zag head moves in steps of h -2 . If p is even, then the zig-zag head reaches the anchor head exactly, moves to ga, and starts moving along the sequence ga, gah, gah 2 , . . . in steps of h. If p is odd, then the zig-zag head reaches the cell gh -1 instead, moves to gah, and starts moving in steps of h as before. The counter head performs the same task, but with the speeds reversed: after reaching the anchor head with speed h -1 , it starts moving from ga in steps of h 2 if p was even, and from gah in steps of h 2 if p was odd. When the counter head reaches the pointer head, the pointer head also moves to ga. It is easy to check that the counter head and the zig-zag head meet at the cell gah p . The counter head stops, and the zig-zag head returns to the pointer head.

Walking on torsion groups

A torsion group is one where every element generates a finite subgroup. In this section, we show that on such groups, non-trivial sparse subshifts cannot be recognized by multi-headed automata. We also show two results about cellular automata and automorphism groups of sparse subshifts on torsion groups. These follow from a curious property, Lemma 3, of CA on sparse subshifts on torsion groups. In its proof, we use the following lemma about finite metric spaces. Lemma 2. Let X be a finite metric space with |X| = k ≥ 2. For all c < diam(X)/(k -1), there exists a nontrivial partition

X = Y ∪ Z with d(Y, Z) > c.
Proof. For a set E ⊂ X, write B E (r) for the closed ball of radius r ≥ 0 around E. Let diam(X) = d(y, z) for some y, z ∈ X. Let X 1 = {y}, and inductively define X i+1 = B Xi (c). For all i ≥ 1 we have either |X i+1 | > |X i | or X i+1 = X i , and in the latter case we have X j = X i for all j ≥ i. It follows that X i = X i+1 holds for some i ≤ k.

If we have X i = X i+1 = X, then diam(X) ≤ (k -1)c, since every element of X, including z, is in the ball B y ((i -1)c) ⊂ B y ((k -1)c). This is a contradiction, so it must be the case that X i = X i+1 = X. Then Y = X i and Z = X \ X i give the desired partition.

Lemma 3. For all torsion groups G, there exists a function d : N 3 → N with the following property. For all k-sparse subshifts X ⊂ S G over all alphabets S 0 with |S| = q + 1, all cellular automata f : X → X with radius r ∈ N, and all x ∈ X, we have

(∃n ∈ N : f n (x) g = 0) =⇒ ∃h ∈ B G (d(k, q, r)) : x gh = 0.
Proof. We prove the existence of such a function d by induction. We define the function so that it is monotone in all the three parameters. Let t G be the order function and T G the torsion function of G.

Case 1: k = 1
First, let k = 1, and let f : X → X be a CA. It is easy to show that if x gh = 0 for all h ∈ B G (r), then f (x) g = 0. Intuitively, this means that nonzero symbols can 'spread' by at most r per time step, and one cannot appear from nowhere. Since X is a k-sparse subshift and k = 1, every point x ∈ X contains at most one nonzero coordinate x g = 0. Intuitively, we want to give an upper bound on how far the nonzero symbol can travel from its initial position g.

By shift-commutation, it is enough to analyze the case x 1 G = 0. Combining the previous observations and the fact |S| = q + 1, it follows from the pigeonhole principle that f n+m (x) = σ R h (f n (x)) for some 0 ≤ n < n + m ≤ q + 1 and h ∈ B G ((q + 1)r). Since f commutes with the shift, we have

f n+ m (x) = σ R h k (f n (x)) for all ∈ N. Since h t G (h) = 1 G , we have f n+t G (h)m (x) = f n (x).
We have shown that f j (x) h = 0 for some j ∈ N implies h ∈ B G ((q + 1)r(1 + t G (h))). Since h ∈ B G ((q + 1)r), we can define d(1, q, r) = (q + 1)r(1 + T G ((q + 1)r)).

Next, consider the case k > 1. To each configuration x ∈ X, we associate the metric space A(x) whose points are the nonzero coordinates of x, and whose distances are those induced by the natural (right) distance in G. We will split the analysis of the dynamics of f on the point x into two cases, depending on whether the diameter of A(f n (x)) stays bounded (by an explicit constant) as n grows.

Intuitively, the idea is that as long as the diameter stays small, we can shrink all the information in x into a single symbol, reducing to the case d(1, •, •), and if the configuration starts expanding, then it splits into two pieces that can never again communicate, and we apply induction to these smaller pieces.

More precisely, define

A(x) = ({g ∈ G | x g = 0}, δ) where δ(g, h) = min{ ∈ N | ∃w ∈ s(G) : h = gw}.
Define also c = 2d(k -1, q, r) + r, and note that since d is monotone, we in particular have c ≥ max 1≤ <k d( , q, r) + d(k -, q, r) + r.

We say that a configuration x ∈ X is clustered if diam(A(x)) ≤ (k -1)c holds, and scattered otherwise.

Case 2: clustered configurations First, suppose x ∈ X and N ∈ N are such that f n (x) is clustered for all n ≤ N . We will give an upper bound on how far nonzero symbols can travel from their original positions in these N steps. Let Z ⊂ X be the subshift generated by the configurations f n (x) for n ≤ N . It is easy to see that every configuration of Z is clustered. Note that that the subshift Z may not be closed under f . Let Y = X {0}∪K , where

K ⊂ L B G ((k-1)c) (Z) is the set of patterns P of shape B G ((k -1)c) occurring in Z such that P 1 G = 0.
Clearly, Y is a 1-sparse subshift, and it should be thought of as a 'compressed' version of Z, where all the nonzero symbols have been encoded into a single coordinate. The idea is to simulate CA f on the compressed subshift Y , and reduce back to the k = 1 case. Let φ : Y → S G be the 'decompression function' defined by

φ(y) h = (y g ) g -1 h , if ∃g ∈ G : y g = 0 ∧ g -1 h ∈ B G ((k -1)c), 0, otherwise.
Let Y = φ -1 (Z), so that φ : Y → Z is a surjective block map. 5 A visualization of φ is shown in Figure 1.

Claim. There exists a (not necessarily unique) cellular automaton f φ : Y → Y such that φ(f φ (y)) = f (φ(y)) holds for all y ∈ Y such that f (φ(y)) ∈ Z.

Intuitively, the CA f φ simulates f on the compressed configurations of Y , as long as their φ-images are clustered.

Proof (of claim).

Observe that for each z ∈ Z and g ∈ G there is at most one configuration y ∈ Y such that y g = 0 and φ(y) = z. Let then 1 = h 1 < h 2 < h 3 < • • • be any total order on the group G, not necessarily in any way compatible with its algebraic structure. Then we can define a map f φ with the desired properties as follows.

First, for the all-0 configuration 0 G ∈ Y , we define f φ (0 G ) = 0 G , and for all y ∈ Y such that f (φ(y)) / ∈ Z, we also define f (y) = 0 G . For all other y ∈ Y , let g ∈ G be the unique element with y g = 0, and let W ⊂ Y be the set of configurations y ∈ Y with φ(y ) = f (φ(y)). The set W is nonempty since φ : Y → Z is surjective, and it is finite because the unique nonzero coordinate of each y ∈ W is among the coordinates gh where h ∈ B G ((k -1)c + r), since we assumed P 1 G = 0 for each P ∈ K. Now, we choose f φ (y) to be the unique configuration y ∈ W with y gh = 0, where h ∈ G is minimal in the ordering h 1 < h 2 < • • • . It is easy to check that f φ is then continuous and shiftcommuting. In fact, from the way we defined it, we see that its radius is at most (k -1)c + r.

Recall the clustered configuration x ∈ S G . We have x ∈ Z by the definition of Z, so there exists a configuration y ∈ Y such that φ(y) = x. By the above claim, we have φ(f n φ (y)) = f n (x) for all n ≤ N . Since Y is a 1-sparse subshift with alphabet of size |K|+1 and f φ is a CA on it with radius at most (k -1)c+r, we have

(∃n : f n φ (y) g = 0) =⇒ ∃h ∈ B G (d(1, |K|, (k -1)c + r)) : y gh = 0 (1)
by Case 1 of this proof. We also remark that if we have N > |K|, then the configuration f n (x) is clustered for all n ∈ N, since there exist i < j ≤ N such that f i φ (φ(y)) is a translated version of f j φ (φ(y)). It remains to prove a variant of the above formula for f , and for that, let f n (x) g = 0 for some g ∈ G. Since the block map φ has radius (k -1)c, we have φ(f n (x)) gh = f n φ (y) gh = 0 for some h ∈ B G ((k -1)c). Equation (1) implies that y gh h = 0 for some h ∈ B G (d(1, |K|, (k -1)c + r)), and from the definition of φ it follows that x gh h = 0 as well, since (y gh h ) 1 G = 0. We have shown that if f n (x) contains a nonzero symbol in some coordinate, then there is a nonzero coordinate in x at distance at most d(1, |K|, (k -1)c + r) + (k -1)c. Note that the cardinality of K is at most exponential in (k -1)c.

Case 3: scattered configurations

Suppose finally that the configuration f n (x) is scattered for some n ∈ N, which we assume to be minimal. By the remark at the end of Case 2, we have n ≤ |K|. We apply Lemma 2 to the metric space A(f n (x)), and obtain a partition for it into sets C, D ⊂ G with distance at least c.

Denote y = f n (x). We define a partition of the configuration y by y = y C + y D , where (y C ) g = y g when g ∈ C and (y C ) g = 0 otherwise, and y D is defined analogously. By the definition of c, we have c ≥ d(|C|, q, r) + d(|D|, q, r) + r. It is then easy to see that f n (y) = f n (y C ) + f n (y D ) for all n ∈ N. In particular, if we have f j (y) g = 0 for some j ∈ N and g ∈ G, then y gh = 0 for some h ∈ B G (max <k d( , q, r)) ⊂ B G (d(k -1, q, r)) by the induction hypothesis. Since we have n ≤ |K| and the CA f has radius r, this implies that x ghh = 0 for some h ∈ B G (r|K|), which implies hh ∈ B G (r|K| + d(k -1, q, r)).

Putting all three cases together, we can define the function d recursively by

d(k, q, r) = d(1, |K|, (k -1)c + r) + (k -1)c + r|K| + d(k -1, q, r)
for all k > 1.

The bounds we give are not very strong, but at least one can check that if the torsion function T G is primitive recursive, then so is the function d.

Theorem 2. If G is finitely generated, infinite and torsion, and X ⊂ S G is sparse and nontrivial, then X / ∈ S(G).

Proof. Let A be a group-walking automaton and Y its associated subshift, and let

X = {x + y | x, y ∈ X, ∀g ∈ G : x g = 0 ∨ y g = 0}.
Since X × Y is sparse, Lemma 3 implies that any head of A can only travel a bounded distance on any configuration of X × Y . Then, for all x ∈ X and all but finitely many g ∈ G, the configuration x + (g • x) is rejected by A if and only if x is. If the support of x is maximal, this configuration is not in X. Thus A does not define X.

Lemma 3 also restricts the structure of the automorphism group of a sparse subshift on a torsion group. Theorem 3. If G is torsion and X ⊂ S G is sparse, then Aut(X) is also torsion.

The last theorem has an obvious converse: if G is not torsion, then the shift along a copy of Z is a non-torsion element of Aut(X) whenever X is sparse and nontrivial. One can construct such examples even in the quotient group Aut(G)/ σ R g | g ∈ G .

Undecidable word problem

If the word problem for G is not necessarily decidable, one can give multiple definitions of Π 0 1 . We give two, both of which correspond to our previous definition of Π 0 1 when the word problem is decidable. Recall that finite patterns are represented computationally as lists of pairs drawn from s(G) * × S. Definition 5. A subshift on G is Π 0 1 if there exists a Turing machine enumerating a set of (possibly inconsistent) forbidden lists of word-symbol pairs for it. Definition 6. A subshift X on G is intrinsically Π 0 1 if there exists an oracle Turing machine that, given an oracle for the word problem of G, enumerates a set of consistent forbidden lists of word-symbol pairs for X.

In [START_REF] Aubrun | A notion of effectiveness for subshifts on finitely generated groups[END_REF], what we call intrinsically Π 0 1 is called G-effective, and this notion was first defined and studied there. Its actual definition in [START_REF] Aubrun | A notion of effectiveness for subshifts on finitely generated groups[END_REF] uses 'group-walking Turing machines', but it is also shown to be equivalent to Definition 6. The following results, the first of which is a direct corollary of Theorem 1, relate these classes of subshifts to the hierarchy of group-walking automata.

Theorem 4. If G is finitely generated, infinite and non-torsion, then S(G, 3) contains the class of Π 0 1 -subshifts. Theorem 5. If G is finitely generated, infinite and non-torsion, then S(G, 4) is exactly the class of subshifts on G which are intrinsically Π 0 1 . Proof. Clearly, all S(G, 4) subshifts are intrinsically Π 0 1 , since a Turing machine with an oracle for the word problem of G can simulate a multi-headed finite state machine on the group. The proof that S(G, 4) contains the intrinsically Π 0 1 subshifts is similar to that of Theorem 1, except that we must simulate a Turing machine with access to an oracle for G. Thus, we only need to describe how one can use four heads to check whether the identity 1 ∼ w holds for an arbitrary w ∈ s(G) * . For this, we use three heads to move by the letters of w, and leave the fourth head as a marker in the cell we started from. We return back on top of the fourth head if and only if 1 ∼ w. We can then move back by w -1 and pick up the fourth head.

From these results, we obtain a characterization of torsion groups. Lemma 4. The X S subshift is intrinsically Π 0 1 on every group. Theorem 6. Let G be a finitely generated infinite group. Then G is torsion if and only if S(G, 4) is not equal to the class of all intrinsically Π 0 1 subshifts. Proof. This follows from Lemma 4, Theorem 5 and Theorem 2.

Finally, we note that Lemma 4 requires the intrinsic notion of computability, as shown by the following corollary of [2, Proposition 2.3] (also proved in [START_REF] Jeandel | Some Notes about Subshifts on Groups[END_REF]).

Proposition 1. Let G be a recursively presented and finitely generated group, and S is a nontrivial finite alphabet. The subshift X G S is Π 0 1 if and only if G has a decidable word problem.

Future work and open questions

While we need four heads in the proof of Theorem 5, we are not able to separate the class S(G, 3) from S(G, 4) on any group G. We do have a general construction which separates these classes on all sufficiently complex torsion groups. Unfortunately, we do not know how to construct a group with the necessary properties, as the construction of torsion groups is quite complicated. Nevertheless, this leads us to believe that the classes are not always equal. Conjecture 1. There exists an infinite finitely generated torsion group G such that S(G, 3) S(G, 4). In particular, S(G, 3) is not always equal to the class of intrinsically Π 0 1 subshifts.

We know that if G is not a torsion group, then the hierarchy S(G, k) k≥1 collapses to the fourth level (if not earlier), and S(G, 4) is exactly the class of intrinsically Π 0 1 subshifts. On torsion groups, the hierarchy never reaches all intrinsically Π 0 1 subshifts, but we have not shown that it is infinite. We believe we have a general construction that proves exactly this, but it is relatively complicated, so for now we only state its conclusion as a conjecture.

Conjecture 2. If G is an infinite finitely generated torsion group, then the hierarchy S(G, k) k≥1 is infinite. Some very basic questions about the abelian cases were left open in [START_REF] Salo | Plane-walking automata[END_REF]. We have no progress on these questions.

Question 1. Do we have S(Z, 2) = S(Z, 3) or S(Z 2 , 2) = S(Z 2 , 3)?

We note that in [START_REF] Delorme | Pebble automata. figures families recognition and universality[END_REF], a slightly different model of multi-headed group-walking automaton is studied on the group Z 2 , and it is shown that in this model, twoheaded machines are strictly weaker than three-headed ones. It seems that the question is harder in our model. In [START_REF] Salo | Plane-walking automata[END_REF], we only showed that S(Z d , 2) S(Z d , 3) holds for d ≥ 3.

  g . A pattern (on G) is a function P ∈ S D , where D = D(P ) is a finite subset of G, called the domain of P . Each pattern P defines a cylinder set [P ] = {x ∈ S G | x| D = P }. The clopen (topologically closed and open) sets in S G are precisely the finite unions of cylinders, and form a basis for the topology.

Definition 4 .

 4 A k-headed group-walking automaton on the full shift S G is a tuple A = ( k i=1 Q i , f, I, F ), where Q 1 , Q 2 , . . . , Q k are state sets not containing the symbol 0, I and F are finite clopen subsets of the product subshift Y = k i=1 X Qi , and f :

Fig. 1 .

 1 Fig.1. The decompression function φ applied to a configuration y ∈ Y . We have chosen G = Z 2 here for simplicity, even though it is not a torsion group. Note that the alphabet of Y consists of certain patterns of X and the symbol 0.

In the earlier article[START_REF] Delorme | Pebble automata. figures families recognition and universality[END_REF], essentially the same observation is made in a slightly different setting on the group Z 2 .

The term 'recursively presented' comes from the fact that one may always assume {wi | i ∈ N} to be a recursive set of words.

The fact that G is torsion prevents us, in general, from defining a bijective version of φ. Also, the subshift Y may be strictly smaller than Y .


Véronique Terrier
email: veronique.terrier@unicaen.fr

Recognition of linear-slender context-free languages by real time one-way cellular automata

A linear-slender context-free language is a context-free language whose number of words of length n is linear in n. Its structure has been finely characterized in a work of Ilie, Rozenberg and Salomaa. Thanks to this characterization, we show that every linear-slender context-free language is recognizable by a real time one-way cellular automaton.

Introduction

One-way cellular automaton (OCA) is one of the simplest parallel recognizing devices. Since its introduction by Dyer [START_REF] Dyer | One-way bounded cellular automata[END_REF], it has been the subject of much interest. Numerous studies have been directed towards the real time OCA, the class of languages decidable in minimal time, and have already provided a good understanding of its abilities and limitations.

In particular, it is known that the real time OCA and the family of context free languages are incomparable [START_REF] Terrier | On real time one-way cellular array[END_REF]. This calls into question which languages they have in common. That is not the case for deterministic CFL: there exits a LL(1) CFL which is not a real time OCA one [START_REF] Okhotin | Comparing linear conjunctive languages to subfamilies of the context-free languages[END_REF]. On the other hand, linear CFL and visible pushdown languages have been proved to be real time OCA ones [START_REF] Čulík | Systolic trellis automata. I, II[END_REF][START_REF] Okhotin | Comparing linear conjunctive languages to subfamilies of the context-free languages[END_REF].

With the aim to identify more common languages, we will take into consideration the counting function that measures the number of words of length n in the language. Noticing that all CFL known to be not real time OCA have their counting function of exponential order, the best is to look at sparse languages. These are the poly-slender CFL whose counting functions are polynomial in n and, more specifically, the linear-slender CFL whose counting functions are linear. The purpose here is to show that linear-slender CFL are real time OCA ones.

The present work essentially relies on a paper by Ilie, Rozenberg and Salomaa which presents a characterization of poly-slender CFL in terms of Dyck loops [START_REF] Ilie | A characterization of polyslender context-free languages[END_REF]. Čulík's OCA which recognizes in real time the language {a n b n+m a m : n, m ≥ 0} and Okhotin's characterization of real time OCA by linear conjunctive grammars will come also into play [START_REF] Čulík | Variations of the firing squad problem and applications[END_REF][START_REF] Okhotin | On the equivalence of linear conjunctive grammars and trellis automata[END_REF].

Preliminary

Basic notions

We first recall some basic definitions and notations.

For any language L, the number of words in L of length n is denoted by n (L). For an integer k,

a language L is k-poly-slender if n (L) is in O(n k ). A language L is poly-slender if L is k-poly-slender for some k. A language L is linear-slender if n (L) is in O(n).
A language L is bounded if there exists a finite number of words

u 1 , u 2 , • • • , u k such that L ⊆ u * 1 u * 2 • • • u * k .
For any word w ∈ Σ + , the primitive root of w is denoted by ρ(w) and corresponds to the minimal word such that w ∈ (ρ(w)) * .

Poly-slender context free languages

We review the definitions and results presented in [START_REF] Ilie | A characterization of polyslender context-free languages[END_REF] that will be fundamental ingredients throughout this paper.

Definition 1 (Dyck loop). Let z = z 1 z 2 • • • z 2k be a Dyck word on {[, ]} of length 2k
. Let l i and r i denote the respective positions of the i-th opening parenthesis [ and its corresponding closing one ] in z. Given some words y 0 ,

• • • , y 2k , x 1 , • • • , x 2k , consider the map h n1,••• ,n k (z 1 z 2 • • • z 2k ) = y 0 x e1 1 y 1 x e2 2 y 2 • • • x e 2k
2k y 2k where each pair of parentheses shares the same exponent:

e li = e ri = n i . A k-Dyck loop is any set D = {h n1,••• ,n k (z 1 z 2 • • • z 2k ) : n i ≥ 0} for some under- lying Dyck word z 1 z 2 • • • z 2k and words x i , y i . Example 1. {ab n1 a(ba) n2+1 a n2+1 (ba) n1+n3+2 b n3 : n 1 , n 2 , n 3 ≥ 0} is a 3-Dyck loop for the underlying Dyck word [[]][] and words y 0 = a, x 1 = b, y 1 = aba, x 2 = ba, y 2 = a, x 3 = a, y 3 = ε, x 4 = ba, y 4 = bab, x 5 = ab, y 5 = a, x 6 = b, y 6 = ε. Example 2. {a n1 b n1+n2 a n2 : n 1 , n 2 ≥ 0} is a 2-Dyck loop for the underlying Dyck word [][] and words x 1 = x 4 = a, x 2 = x 3 = b, y 0 = y 1 = y 2 = y 4 = ε.
The structure of poly-slender CFL finely corresponds to Dyck loops: Theorem 1. For any k ≥ 0, a context-free language is k-poly-slender if and only if it is a finite union of (k + 1)-Dyck loops.

The following notion captures whether the position of some word w can be distinguished or not.

Definition 2 (Link). Let u, v ∈ Σ + and w ∈ Σ * . The word w links u with v (link(u, w, v)) if and only if ρ(u)w = wρ(v). That means ρ(u) = pq, ρ(v) = qp and w = (pq) * p for some p, q. And so u m wv n is a prefix of (pq) * Example 3. With x i and y i as defined in Example 1, link(x 4 , y 4 , x 5 ) holds but link(x i , y i , x i+1 ) does not hold for i = 1, 2, 3, 5. With x i and y i as defined in Example 2, link(x 2 , y 2 , x 3 ) holds but neither link(x 1 , y 1 , x 2 ) nor link(x 3 , y 3 , x 4 ) holds.

We will make great use of the following lemma: Lemma 1. Consider some words x i ∈ Σ + and y i ∈ Σ * , and some non-negative integers n i , m i . Denote w = y 0 x n1

1 y 1 x n2 2 y 2 • • • x nr r y r , w = y 0 x m1 1 y 1 x m2 2 y 2 • • •
x mr r y r and assume that link(x i , y i , x i+1 ) holds for no i. Then there is a constant N 0 , depending only on the lengths of the words x i and y i , such that, if n i , m i are larger than N 0 and there is i with n i = m i , then w = w .

For a general overview, we recall the result of Latteux and Thierrin [START_REF] Latteux | On bounded context-free languages[END_REF] and the one of Ginsburg and Spanier [START_REF] Ginsburg | Bounded algol-like languages[END_REF]: Theorem 2. A context-free language is poly-slender if and only if it is bounded. Theorem 3. The family of bounded languages is the smallest family which contains all finite languages and is closed under the following operations:

1. union 2. catenation 3. (x, y) L = n≥0

x n Ly n for any x, y words

Real time one-way cellular automaton

A one-way cellular automaton is a one-dimensional array of finite automata (the cells) indexed by N. The cells evolve synchronously at discrete time steps. Each cell takes one value from a finite set of states Q. At each step, the evolution of a cell is defined by its own state and the state of its right neighbor according to a transition function δ. Formally, denoting c, t the state of the cell c at time t, c, t

+ 1 = δ ( c, t , c + 1, t ).
In order that an OCA acts as a language recognizer, we specify two subsets of Q: the alphabet Σ of input symbols and the set of accepting states Q accept . The input mode is parallel. At initial time 0, the i-th bit of the input word w ∈ Σ * is fed to the cell i: i, 0 = w i . An OCA is said to accept (resp. reject) a word w in real time, if on input w the cell 0 enters an accepting (resp. non-accepting) state at time |w| -1. It corresponds to the minimal time for the cell 0 to know the whole input. A language is a real time OCA language if there exists some OCA (Q, Σ, Q accept , δ) which accepts in real time exactly the words w ∈ L.

The computation of an OCA is usually represented by a time-space diagram (see Fig 1). The t-row corresponds to the cellular array at time t. Only those sites involved in the real time computation are depicted. As a matter of fact, there are two topologically equivalent ways to display the time-space diagram. We will use here the bilateral symmetric layout, i.e., the right one. The real time OCA class is robust: introducing the notion of conjunctive grammar, Okhotin has exhibited a characterization of real time OCA in terms of a generating device [START_REF] Okhotin | On the equivalence of linear conjunctive grammars and trellis automata[END_REF]. Let us recall its statement, it will be one of the main ingredients in this paper. An alternating grammar is a grammar enhanced with a conjunctive operation symbolized by &. Denoting N the set of variables and Σ the set of terminals, each production is of the form

A → α 1 & • • • & α k where A ∈ N and α 1 , • • • , α k ∈ (A ∪ Σ) * .
Such a production denotes that the language generated by A is the intersection of the languages generated by α 1 , • • • , α k . Analogously to linear context free grammars, a linear conjunctive grammar is defined as an alternating grammar with the restriction that for every production

A → α 1 & • • • & α k ,
no α i has more than one instance of a variable. An algorithm describing how to recognize any linear CFL on a real time OCA was already known [START_REF] Čulík | Systolic trellis automata. I, II[END_REF]. More radically, to extend linear context free grammars with the conjunctive operation & leads to a complete characterization of real time OCA [START_REF] Okhotin | On the equivalence of linear conjunctive grammars and trellis automata[END_REF]: Theorem 4. A language L is recognized in real time by an OCA if and only if L is generated by a linear conjunctive grammar.

Let us recall the conversion from a real time OCA to a linear conjunctive grammar that we will need later. See Fig. 2 to get some insight about the translation.

Lemma 2. Given any language L recognizable by some real time OCA A = (Q, Σ, Q accept , δ), L is generated by the linear conjunctive grammar G = (Σ, {S} ∪ {A q : q ∈ Q}, S, R) where R contains the following rules:

S → A q for all q ∈ Q accept A a → a for all a ∈ Σ A δ(g,d) → A g b & cA d for all g, d ∈ Q and all b, c ∈ Σ
At last, let us give some examples and properties of real time OCA to illustrate their abilities and limits. The Dyck language, the linear-slender CFL {a n b n+m a m : n, m ≥ 0}, the inherently exponentially ambiguous CFL L * with L = {a i b j c k : i = j or j = k} [START_REF] Naji | Ambiguity of context-free languages as a function of the word length[END_REF], the non CFL languages {a n b n c n : n ≥ 0} and {a n b 2 n : n ≥ 0} with a non semilinear Parikh image, are all real time OCA languages. In addition, real time OCA languages include all linear CFL and visible

δ(g, d) g d c • • • w • • • b cw ∈ LG(Ag) wb ∈ LG(A d ) cwb ∈ LG(A δ(g,d) ) Fig. 2. The OCA's transition δ(g, d) is converted into the rule A δ(g,d) → Agb & cA d
pushdown languages [START_REF] Čulík | Systolic trellis automata. I, II[END_REF][START_REF] Okhotin | Comparing linear conjunctive languages to subfamilies of the context-free languages[END_REF]. On the other hand, several languages are known not to be real time OCA: all non regular languages over a one letter alphabet, the inherently ambiguous CFL L 1 L 1 square of the linear CFL [START_REF] Terrier | On real time one-way cellular array[END_REF][START_REF] Terrier | Language not recognizable in real time by one-way cellular automata[END_REF][START_REF] Okhotin | Comparing linear conjunctive languages to subfamilies of the context-free languages[END_REF]. Further, the real time OCA class is closed under boolean operations, reverse, operation (the one defined in Theorem 3), left and right concatenation with regular languages. The proofs are folklore. A contrario, the real time OCA class is not closed under morphism, concatenation, Kleene star and cycle [START_REF] Čulík | Systolic trellis automata: Stability, decidability and complexity[END_REF][START_REF] Terrier | On real time one-way cellular array[END_REF][START_REF] Terrier | Closure properties of cellular automata[END_REF].

L 1 = {1 k 0u10 k : k > 0, u ∈ {0, 1} * }, the language {uvu : u, v ∈ {0, 1} * , |u| > 1}, the determin- istic CFL (to be more precise: LL(1) language) {c m a l0 ba l1 b • • • a lm b • • • a lz bd n : m, n, l i ≥ 0, z ≥ 1, l m = n} [1,

Poly-slender context free languages and real time one-way cellular automata

The question behind this paper is whether the poly-slender CFL are real time OCA languages. According to Theorem 3, the poly-slender CFL are the smallest family which contains all finite languages and is closed under union, concatenation and operation. Of course, real time OCA languages include all finite languages and are closed under union and operation. This is easy to prove using the grammar characterization of real time OCA. The problematic point is concatenation: can we assert that the concatenation of two Dyck loops is a real time OCA language? We do not answer this question but in the simple case: 1-Dyck loops. Precisely we will show the following result:

Theorem 5. Linear-slender context-free languages are recognizable in real time by one-way cellular automata.

The rest of the paper will be devoted to the proof of this theorem. Concretely we have to show that 2-Dyck loops are recognized in real time by OCA.

As an introduction, we may observe that 1-Dyck loops are real time OCA languages. Indeed a 1-Dyck loop corresponds to a set D = {y 0 x n 1 y 1 x n 2 y 2 : n ∈ N} for some words y 0 , x 1 , y 1 , x 2 , y 2 . It is a linear CFL and so it is a real time OCA language. As a consequence, all constant-slender languages are real time OCA languages.

Let us now consider 2-Dyck loops. According to whether the underlying Dyck word is [[]] or [][], they are of shape {y

0 x n1 1 y 1 x n2 2 y 2 x n2 3 y 3 x n1 4 y 4 : n 1 , n 2 ≥ 0} or {y 0 x n1 1 y 1 x n1 2 y 2 x n2 3 y 3 x n2 4 y 4 : n 1 , n 2 ≥ 0}
A first simplification is to assume that the two ends y 0 and y 4 are empty knowing that if L is a real time OCA language then so is {y 0 }L{y 4 } whatever the words y 0 and y 4 are. We will suppose also that the words x i are non-empty, the degenerate cases being easy to handle.

The underlying Dyck word is [[]].

That is the simple case. The corresponding Dyck loop {x n1 1 y 1 x n2 2 y 2 x n2 3 y 3 x n1 4 : n 1 , n 2 ≥ 0} is clearly a linear CFL and so it is real time OCA recognizable. Here it is basically the closure under the operation which is involved.

The underlying Dyck word is [][].

Now it is the closure under concatenation of 1-Dyck loops which is involved.

Case 1. link(x i , y i , x i+1 ) holds for no i = 1, 2, 3

Let N 0 be a constant as defined in Lemma 1. The Dyck loop can be divided into three subsets D 1 , D 2 and D 3 , where

D 1 = {x n1 1 y 1 x n1 2 y 2 x n3 3 y 3 x n3 4 : n 1 < N 0 , n 3 ∈ N}, D 2 = {x n1 1 y 1 x n1 2 y 2 x n3 3 y 3 x n3 4 : n 1 ∈ N, n 3 < N 0 }, D 3 = {x n1 1 y 1 x n1 2 y 2 x n3 3 y 3 x n3 4 : n 1 , n 3 ≥ N 0 }. Observe that D 1 = 0≤i<N0 {x i 1 y 1 x i 2 y 2 x n 3 y 3 x n 4
: n ∈ N} is a finite union of linear CFL's and thus is alinear CFL. The subset D 2 is as well a linear CFL. Further, Lemma 1 ensures that D 3 can be specified as the intersection of two linear CFL's :

D 3 = {x n1 1 y 1 x n1 2 y 2 x n3 3 y 3 x n4 4 : n 1 , n 3 , n 4 ≥ N 0 } ∩ {x n1 1 y 1 x n2 2 y 2 x n3 3 y 3 x n3 4 : n 1 , n 2 , n 3 ≥ N 0 }
and so is real time recognizable by an OCA.

Case 2. link(x i , y i , x i+1 ) holds for one i = 1, 2, 3

The case where y 1 links x 1 with x 2 (or in a symmetric way y 3 links x 3 with x 4 ) does not present any difficulty. By Definition 2, y 1 links x 1 with x 2 if ρ(x 1 ) = pq, ρ(x 2 ) = qp and y 1 = (pq) γ p for some words p, q and integer γ. Setting x 1 = (pq) α , x 2 = (qp) β , x n1 1 y 1 x n2 2 y 2 can be rewritten as (pq) (α+β)n1+γ py 2 and thus specifies a regular language. Moreover x n3 3 y 3 x n4 4 = x n3 3 y 3 x n3 4 corresponds to a linear CFL. Their concatenation is linear CFL and so real time recognizable by an OCA.

It remains to examine the most technical case where y 2 links x 2 with x 3 but link(x i , y i , x i+1 ) does not hold for i = 1 and i = 3. As y 2 links x 2 with x 3 there exists some p, q and α, β, γ such that x 2 = (pq) α , x 3 = (qp) β and y 2 = (pq) γ p. Then x n1 1 y 1 x n2 2 y 2 x n3 3 y 3 x n4 4 can be rewritten as x n1 1 y 1 (pq) αn1+βn3+γ py 3 x n3 4 . Setting z 1 = x 1 , z 2 = y 1 , z 3 = pq, z 4 = py 3 , z 5 = x 4 , such 2-Dyck loops can be reshaped into z n1 1 z 2 z αn1+βn3+γ 3 z 4 z n3 5 with the properties that z 2 does not link z 1 with z 3 and, readily verifiable, z 4 does not link z 3 with z 5 . So our task is to show that {z n 1 z 2 z αn+βm+γ 3 z 4 z m 5 : n, m ≥ 0} is a real time OCA language. It will be done in two steps:

1. Given a five letters alphabet A = {a 1 , • • • , a 5 }, whatever α, β ≥ 1 and γ ≥ 0 are, we will present a real time OCA which recognizes the language L α,β,γ = {a n 1 a 2 a αn+βm+γ 3 a 4 a m 5 : n, m ≥ 0}. 2. For any homomorphism h on A such that neither link(h(a 1 ), h(a 2 ), h(a 3 ))

nor link(h(a 3 ), h(a 4 ), h(a 5 )) holds, we will verify that h(L α,β,γ ) is a real time OCA language.

Proposition 1. The language L α,β,γ = {a n 1 a 2 a αn+βm+γ 3 a 4 a m 5 : n, m > 0}, where the symbols a 1 , • • • , a 5 are distinct, is recognizable in real time by an OCA.

Proof. The main ingredient is Čulík's OCA which recognizes in real time the language {a n b n+m a m : n, m ≥ 0} [START_REF] Čulík | Variations of the firing squad problem and applications[END_REF]. His construction makes ingenious use of a firing squad synchronization. Let us begin by recalling the process (see Fig. 3). For convenience, we identify the sites of the OCA with integer coordinates (x, y) where x + y is even. In this way, the input symbols are placed at positions (2x, 0). The unique symbol a 2 is chosen to be at the origin (0, 0) and, when the input is of shape a + 1 a 2 a j 3 a 4 a + 5 , the unique symbol a 4 is at (2j + 2, 0). The process is set up using a firing squad synchronization with two generals G g and G d located according to the unique symbols a 2 and a 4 . Precisely, the left general G g is at [START_REF] Čulík | Systolic trellis automata. I, II[END_REF][START_REF] Dyer | One-way bounded cellular automata[END_REF] and the right general G d at (2j -1, 5). Thus the synchronization occurs at points (1 + 2k, 1 + 2j) for all k with 0 < k < j. We check that the k-th firing points (1 + 2k, 1 + 2j) corresponds to the output of the input subword which begins at (2(k -j), 0) and ends at (2(1 + j + k), 0), namely the subword a j-k 1 a 2 a j 3 a 4 a k 5 . Next, Čulík showed that the construction can be adapted to recognize the languages {a i b j a k : i, k ≥ 0, mj + c = i + k} for all m ≥ 1, c ≥ 0. Actually, the same approach works in these more general settings: it exists a real time OCA deciding the language L α,β,γ = {a i 1 a 2 a j 3 a 4 a k 5 : i, j, k ∈ N, j = αi + βk + γ} for every non-negative rational numbers α, β, γ. Let us outline the modified construction. Be warned that we will use rational coordinates but the technique to revert to an OCA diagram is standard. Firstly observe that we may reduce the range of the synchronization in locating the two generals later: with the left general G g at (3 + γ, 5 + γ) and the right general G d at (2j -1 -γ, 5 + γ), the set of firing points becomes {(1 + 2k + γ, 1 + 2j -γ) : k ∈ N, 0 < k < j -γ}. We explain now the construction in terms of geometric transformations. It will be achieved by the composition of two directional scalings (see Fig. 4). Initiated from the unique symbol a 2 , the first transformation starts at point (0, 0) and applies on its cone of consequences {(c, t) : |c| ≤ t}, i.e., the future light cone of (0, 0) which encompasses the set of points impacted by (0, 0). It leaves the line t = c stable and scales by the factor 1/α in the up-left to downright direction according to the map M g = (1+α)/(2α) (α-1)/(2α) (α-1)/(2α) (1+α)/(2α) . Observe that the transformation is workable. Inside the cone, the neighborhood constraints are satisfied. The right side of the cone is stable. And the computation on the subword a + 1 occurring below the left side can easily be scaled. The second transformation is symmetric. Initiated from the unique symbol a 4 , it starts at point (2j + 2, 0) and applies on its cone of consequences {(c, t) : |c -2j -2| ≤ t}. It leaves the line t + c = 2j + 2 stable and scales by the factor 1/β in the up-right to down-left direction according to the map Now, the composition of these two scalings applies inside the cone of consequences of (j +1, j +1): {c, t) : |c-j -1| ≤ t-j -1}, intersection of the two cones issued from a 2 and a 4 . See Fig. 5. It corresponds to the affine transformation with origin (j + 1, j + 1) and matrix M = M g × M d = (α+β)/(2αβ) (α-β)/(2αβ) (α-β)/(2αβ) (α+β)/(2αβ) . Thus the firing points {(1+2k +γ, 1+2j -γ) : k ∈ N, 0 < k < j -γ} being inside the cone of (j + 1, j + 1) are mapped to the points {(1 + j -(j -k -γ)/α + k/β, 1 + j + (j -k -γ)/α + k/β) : k ∈ N, 0 < k < j -γ}. Among these points, some of them match OCA's sites providing k/β and (j -k -γ)/α are integers. Moreover such a point, with (j -k -γ)/α, k/β ∈ N, corresponds to the output of the input subword that begins at (2(j -k -γ)/α, 0) and ends at (2j + 2 + 2k/β, 0), i.e., the subword a n 1 a 2 a j 3 a 4 a m 5 with n = (j -k -γ)/α, m = k/β. To conclude just note that αn + βm + γ = j. Proposition 2. For any homomorphism h on A such that neither link(h(a 1 ), h(a 2 ), h(a 3 )) nor link(h(a 3 ), h(a 4 ), h(a 5 )) holds, h(L α,β,γ ) is a real time OCA language.

M d = (1+β)/(2β) (1-β)/(2β) (1-β)/(2β) (1+β)/(2β) .
Proof. One has to be careful because real time OCA is not closed under morphism: each recursively enumerable language can be written as the image of a real time OCA language by a morphism [START_REF] Čulík | Systolic trellis automata: Stability, decidability and complexity[END_REF]. But here we play with the image of languages with very simple structure.

First observe that h({a n 1 a 2 a αn+βm+γ 3 a 4 a m 5 : n < N 0 or m < N 0 }) is a linear CFL, so to show that h({a n 1 a 2 a αn+βm+γ 3 a 4 a m 5 : n, m ≥ N 0 }) is a real time OCA language will suffice. According to Proposition 1, there exists a real time OCA (Q, A, Q accept , δ) which recognizes the language L = {a n 1 a 2 a αn+βm+γ 3 a 4 a m 5 : n, m ≥ N 0 }. Following Okhotin [START_REF] Okhotin | On the equivalence of linear conjunctive grammars and trellis automata[END_REF], L is defined by the linear conjunctive grammar G = (A, {S} ∪ {A q : q ∈ Q}, S, R) where R contains the following rules:

S → A q for all q ∈ Q accept A a → a for all a ∈ A A δ(g,d) → A g b & cA d for all g, d ∈ Q and all b, c ∈ A

1 Fig. 1 .

 11 Fig. 1. Time-space diagram of a real time OCA

5 a j-k 1 Fig. 3 .

 513 Fig. 3. Čulík's OCA

3 Fig. 4 .

 34 Fig. 4. Two scalings

1 Fig. 5 .

 15 Fig. 5. Composition of two scalings

Now let us make explicit, in the grammar rules, the bounded feature of the language. All words are of shape a + 1 a 2 a + 3 a 4 a + 5 . We denote by Follow(i) the set of j such that a j follows immediately a i in the expression a + 1 a 2 a + 3 a 4 a + 5 :

r, j) for all g, d ∈ Q and all i, j, r, s with 1 ≤ i ≤ r ≤ s ≤ j ≤ 5, r ∈ Follow(i), j ∈ Follow(s)

To gain a better understanding of the last derivation rule, see Fig. 6, it depicts the corresponding OCA transition. With such refinements, we get that L G (A q , i, j) is the subset of L G (A q ) whose words begin with a i , ends with a j and which are factors of a + 1 a 2 a + 3 a 4 a + 5 .

In addition, to meet later requirements, we replace all rules (A ai , i, i) → a i with the rules (A δ(ai

1 a 2 a N0 3 a 4 a N0 5 . It does not alter the expressiveness of the grammar.

Finally, in replacing each symbol a i with its image h(a i ), G is rewritten to H = (Σ, {S} ∪ {(A q , i, j) : q ∈ Q, 1 ≤ i ≤ j ≤ 5}, S, R ) where R contains the following rules:

Clearly, h(L G (S)) ⊆ L H (S). Let us ensure that they are equal and, more specifically, that L H (A, i, j) ⊆ h(L G (A, i, j)) for every variable (A, i, j). The proof is done by induction on the height of the parse trees. The inductive assumption is that all words generated within H by a tree of height h and root node (A, i, j) are images by h of words generated within G by a tree of height h and root node (A, i, j).

The base case. The trees of height 1 within H display the derivations

The inductive step. We focus on the trees with root node (A q , 1, 5) and omit the ones with root (A q , i, j) when i > 1 or j < 5 that are easier to handle. Given any tree T within H of height h + 1 > 1 and root (A q , 1, 5). The root node expands into two subtrees of height at most h according to some rule (A q , 1, 5) → (A g , 1, s)h(a 5 ) & h(a 1 )(A d , r, 5) where δ(g, d) = q, s is 4 or 5 and r is 1 or 2. By assumption, (A g , 1, s) produces the image by h of a word a n1 1 a 2 a n2 3 a 4 a n3