Martin Kutrib

Andreas Malcher

Matthias Wendlandt

Fast One-Way Cellular Automata with Reversible Mealy Cells

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

Introduction

The study of computational devices performing reversible computations is mostly motivated by the physical observation that a loss of information yields heat dissipation [START_REF] Landauer | Irreversibility and heat generation in the computing process[END_REF]. To avoid such situations computations are of interest in which every configuration has a unique successor configuration as well as a unique predecessor configuration so that at every point of the computation no information gets lost. Reversibility has been studied for many computational devices starting with Bennett's investigations for Turing machines in [START_REF] Bennett | Logical reversibility of computation[END_REF] where it is shown that for every (possibly irreversible) Turing machine an equivalent reversible Turing machine can be constructed. A similar result has been obtained for deterministic space-bounded Turing machines, in particular, deterministic linear bounded automata by Lange, McKenzie, and Tapp in [START_REF] Lange | Reversible space equals deterministic space[END_REF]. For deterministic pushdown automata and deterministic queue automata the situation is different: in both cases it is possible to show (see, for example, [8,[START_REF] Kutrib | Reversible queue automata[END_REF]) that the reversible variant is weaker than the general model, that is, there are languages which can be accepted by the general model, but not by its reversible variant. In these cases, the loss of information in computations is inevitable. For deterministic multihead finite automata the picture is split: for two-way multi-head finite automata Morita has shown in [START_REF] Morita | Two-way reversible multi-head finite automata[END_REF] that the general model and the reversible model coincide. On the other hand, in case of one-way motion it is shown in [START_REF] Kutrib | One-way reversible multi-head finite automata[END_REF] that the reversible model is weaker than the general model. Reversible computations in deterministic finite automata have been introduced in [2] and it is shown in [START_REF] Pin | On reversible automata[END_REF] that there are regular languages which cannot be accepted by any (one-way) reversible deterministic finite automaton. However, if two-way motion of the input head is allowed, it is known due to [5] that the general model and the reversible model coincide. A structural approach to reversible computing not depending on specific computational models has been proposed in [1].

For cellular automata (CA), the notion of reversibility has been investigated from several points of view. One fundamental result is that the reversibility of a cellular automaton is equivalent to the injectivity of the global transition function. Moreover, the injectivity of the global transition function is decidable for one-dimensional CAs, but becomes undecidable in higher dimensions. Details and literature for these results may be found in the survey paper [START_REF] Kari | Theory of cellular automata: a survey[END_REF]. The question whether every cellular automaton can be made reversible has been answered in the affirmative first by Toffoli who shows in [START_REF] Toffoli | Computation and construction universality of reversible cellular automata[END_REF] that every k-dimensional CA can be simulated by a (k + 1)-dimensional reversible CA. This result has been improved by Morita and Harao in [START_REF] Morita | Computation universality of one dimensional reversible injective cellular automata[END_REF] where it is shown that every reversible Turing machine can be simulated by a one-dimensional reversible CA. By introducing the notion of partitioned cellular automata further improvements are given by Morita in [14,[START_REF] Morita | Reversible simulation of one-dimensional irreversible cellular automata[END_REF] where, for example, the latter result is shown to hold also for one-dimensional one-way reversible CAs. More results on reversible CAs may be found in the survey paper [START_REF] Morita | Reversible computing and cellular automata -A survey[END_REF].

In the context of language recognition, cellular automata are working on finite configurations with fixed boundary conditions. With regard to reversible computations, it is clear that reversibility in such devices cannot be defined on the injectivity of the global transition function. Thus, one considers computations that are reversible on the core of computation, namely, starting in the initial configuration and ending in the configuration given by the time complexity. From this point of view, language recognition by reversible devices has been studied for real-time two-way CAs [6], for real-time iterative arrays [7], and more recently for real-time one-way CAs [10]. Another recent result is provided by Morita in [START_REF] Morita | Language recognition by reversible partitioned cellular automata[END_REF] where it is shown that every deterministic linear bounded automaton can be simulated by a reversible CA working on finite configurations with fixed boundary conditions.

In this paper, we consider another aspect of reversibility. In all cellular models studied so far the reversibility concerns configurations, that is, from every configuration the successor as well as the predecessor configuration can be computed in a unique way. Since CAs are basically arrays of interacting deterministic finite automata, one can also consider the reversibility of the single deterministic finite automata, that is, of the local transition function, and we will speak in this context of locally reversible CAs. For partitioned cellular automata and unbounded computations it is known [START_REF] Morita | Reversible simulation of one-dimensional irreversible cellular automata[END_REF][START_REF] Morita | Computation universality of one dimensional reversible injective cellular automata[END_REF] that such automata are globally reversible if and only if they are locally reversible if and only if they are locally in-jective. Apart from a theoretical interest in locally reversible computations, there is also a practical interest to investigate such CAs, since in this case the devices are composed of reversible components. Here, we will study local reversibility with regard to language recognition for weak cellular devices, namely, we will focus on real-time computations in one-way CAs (OCAs). Moreover, we consider OCAs having Mealy automata in their cells instead of deterministic finite automata. This generalization allows in particular a comparison with the notion of partitioned cellular automata. The paper is organized as follows. In Sect. 2 we summarize basic notions and introduce weakly and strongly reversible Mealy automata which are subsequently used to define one-way Mealy cellular automata with weakly or strongly reversible cells. Moreover, we provide an example of a non-semilinear language that is accepted by some real-time OCA with strongly reversible cells. Sect. 3 is devoted to investigating real-time OCAs with weakly reversible cells and it turns out that every real-time OCA can be converted to the former model. This means that every real-time OCA computation can be simulated by a real-time OCA with weakly reversible cells. In Sect. 4 we study reversible one-way partitioned CAs working in contrast to [14] on finite configurations with fixed boundary conditions. We first discuss how this notion is related to our concept of Mealy cellular automata. Then, it is shown that every regular language (reversible or not) is accepted by such automata. Moreover, it is possible to accept a certain context-free, non-regular language. Finally, we give a short conclusion. We would like to note that some proofs are omitted due to space considerations.

Preliminaries and Definitions

We denote the set of non-negative integers by N. The reversal of a word w is denoted by w R . For the length of w we write |w|. We write ⊆ for set inclusion, and ⊂ for strict set inclusion. In order to avoid technical overloading in writing, two languages L and L are considered to be equal, if they differ at most by the empty word. Throughout the article two devices are said to be equivalent if and only if they accept the same language.

A deterministic finite Mealy automaton (DFMA) is a deterministic finite automaton that emits a symbol during each transition performed. So, it is particularly composed of a finite state set S, a finite input alphabet A, a finite output alphabet B, and a partial transition function δ that maps from S × A to S × B. In this way, the new state and the symbol emitted during a transition are given. Let π S denote the projection on the first component and π B denote the projection on the second component of pairs from S × B. A state in a DFMA is called a sink state, if the state can never be left once entered.

A DFMA is said to be weakly reversible (WREV-DFMA) if every pair (a, b) from A × B induces an injective partial mapping from the state set S to itself via the mapping δ (a,b) : S → S (see Figure 1). A WREV-DFMA can also be considered as a (partial) permutation automaton.

A DFMA is said to be strongly reversible (SREV-DFMA) if every letter a from A induces an injective partial mapping from the state set S to itself via the mapping δ a : S → S where δ a (s) = s if and only if s = π S (δ(s, a)). In this case, the reverse transition function δ ← induces for every letter a from A a (partial) injective function δ ← a : S → S. The property of being strongly reversible is also known as being codeterministic.

s 0 s 1 s0 s1 0, 0 0, 0 0, 0 0, 0 1, 0 1, 1 1, 0 1, 0 1, 1 1, 1
Fig. 1. A weakly reversible deterministic finite Mealy automaton, where an edge from p to q labeled by a, b means δ(p, a) = (q, b). Example transitions are δ(s1, 1) = (s0, 1),

δ (1,1) (s1) = s0, δ ← (s0, 1, 1) = s1 and δ ← (1,1) (s0) = s1.
Next, we consider one-way cellular automata whose cells are DFMAs. A oneway cellular automaton with Mealy cells (one-way Mealy cellular automaton) is a linear array of identical deterministic finite Mealy machines, called cells. Except for the rightmost cell each one is connected to its nearest neighbor to the right. The state transition of a cell depends on its current state and the latest output that has been emitted by its neighbor. We say that this output is the message sent to the neighbor. Initially, a distinguished initial message is sent. The rightmost cell receives information associated with a boundary symbol on its free input line. The state changes take place simultaneously at discrete time steps. The input mode for cellular automata is called parallel. One can suppose that all cells fetch their input symbol during a pre-initial step.

Formally, a one-way Mealy cellular automaton (OMCA) is a system given as S, F, A, B, ⊥, #, δ , where S is the finite, nonempty set of cell states, F ⊆ S is the set of accepting states, A ⊆ S is the nonempty set of input symbols, B is the finite, nonempty set of messages, ⊥ ∈ B is the initial message, # ∈ B is the boundary message, and δ : S × B → S × B is the local transition function.

A configuration of a one-way Mealy cellular automaton S, F, A, B, ⊥, #, δ is a mapping c : {1, 2, . . . , n} → (S × B), for n ≥ 1, that assigns a state and a message to each cell, where it is understood that the state is the current state of the cell and the message is the latest message sent by its neighbor. As before, given some c(i) = (s, m), the projection on its state part s is denoted by π S (c(i)) and the projection on its message part m is denoted by π B (c(i)). The operation starts in a so-called initial configuration, which is defined by the given input w = a 1 a 2 • • • a n ∈ A + . We set c 0 (i) = (a i , ⊥), for 1 ≤ i ≤ n -1, and c 0 (n) = (a n , #). Successor configurations are computed according to the global transition function ∆. Let c be a configuration with n ≥ 1, then the successor configuration c is

c = ∆(c) ⇐⇒    π S (c (i)) = π S (δ(c(i))), i ∈ {1, 2, . . . , n} π B (c (i)) = π B (δ(c(i + 1))), i ∈ {1, 2, . . . , n -1} π B (c (n)) = # .
An input w is accepted by a one-way Mealy cellular automaton M if at some time step during the course of its computation the leftmost cell enters an accepting state. The language accepted by M is denoted by L(M ). If all w ∈ L(M ) are accepted with at most |w|+1 time steps, then M is said to operate in real-time. The family of languages accepted by some device X operating in real-time is denoted by L rt (X).

Note that the state transitions of cells in an OMCA depend on the current state and the latest output symbol emitted by the neighbor. So, taking a single cell as DFMA, its input alphabet is equal to its output alphabet B. Now the structural restriction of one-way Mealy cellular automata we are interested in is that the single cells have to be reversible deterministic finite Mealy automata. These cellular automata are referred to by one-way Mealy cellular automata with strongly or weakly reversible cells and are denoted by SRC-OMCA and WRC-OMCA. In general, the transition functions for reversible deterministic finite Mealy automata may be partial in order to cope with situations that would drive the automaton into a rejecting sink state. Instead of entering the sink state, now the DFMA simply stops and rejects since it could not process the input entirely. However, since the concept of cellular automata does not allow single cells to stop, here, a rejecting sink state of the cells cannot be avoided in general. So, we slightly soften the notion of reversibility by disregarding rejecting sink states and say that an OMCA is an RC-OMCA if its cells are deterministic finite automata that are reversible with the exception of a possible rejecting sink state. However, it turns out in the next section that the disregarding of rejecting sink states is no restriction at least for WRC-OMCAs.

These definitions are justified and compared with related concepts after the following example that should clarify the notation.

Example 1. The non-semilinear language { a n b k•2 n | k, n ≥ 1 } is accepted by the following one-way Mealy cellular automaton with strongly reversible cells M = S, F, {a, b}, B, ⊥, #, δ in real time. We set S = {a, a 1 , b, s -, s + }, where B = {1, 0, s, s -, s + , ⊥, #}, F = {s + }, is the sole accepting state, and s -is a rejecting sink state. The transition function δ is defined through: and δ(s -, x) = (s -, s -) and δ(s + , x) = (s -, s -), for all x ∈ B.

By inspecting the transition function, it is verified that the cells are in fact SREV-DFMAs. An example computation on input a 3 b 8 is depicted in Figure 2. Basically, the consecutive b-cells stay in their state, where message 1 is transmitted in every step. Additionally, a message s is sent by the rightmost cell upon receiving the border message. This message moves through the b-cells one cell per time step.

The consecutive a-cells set up a binary counter with the least significant bit in the rightmost a-cell. To this end, state a is used to represent digit zero and state a 1 is used to represent digit one. A message 1 indicates a carry-over and a message 0 indicates no carry-over. Finally, when the signal s meets the a-cells, it becomes signal s + as long as it only sees digits one, that is, states a 1 . Otherwise, it turns to signal s -which is rejecting.

So, in order to accept an input, the leftmost cell has to enter state s + . This is only possible if message s + has moved through a counter that represents a binary number of the form 1 n , that is, 2 n -1. Since due to the initial step, the counter starts to increase at time step one, this is only possible if message s has passed through a sequence of b-cells whose length is a multiple of 2 n . Another related concept has been studied in [10]. Based on the observation, that in reversible one-way cellular automata information flow is from right to left in a forward computation and from left to right in a backward computation, a one-way cellular automaton is said to be reversible if there exists a reverse local transition function that computes the predecessor states. Due to the domain S 2 and the range S, obviously, the local transition function cannot be injective in general. However, since for reverse computation steps the flow of information is reversed as well, for the reverse transition function, each cell receives the state of its left neighbor. For example, let s 1 s 1 s 2 s 1 be the states of four adjacent cells, and δ(s 1 , s 1 ) = s 1 , δ(s 1 , s 2 ) = s 2 , and δ(s 2 , s 1 ) = s 1 , then the successor states of the three left cells are s 1 s 2 s 1 . So, for the reverse transition function δ R we obtain δ R (s 1 , s 2 ) = s 1 and δ R (s 2 , s 1 ) = s 2 and, thus, such a behavior is possible in reversible one-way cellular automata. However, the single cell is not a reversible finite automaton, since δ ← (s 1 , s 1 ) = s 1 and δ ← (s 1 , s 1 ) = s 2 . On the other hand, let s 1 s 2 s 2 as well as s 2 s 3 s 3 be the states of three adjacent cells, and δ(s 1 , s 2 ) = s 1 , δ(s 2 , s 2 ) = s 2 , δ(s 2 , s 3 ) = s 1 , and δ(s 3 , s 3 ) = s 2 . Then the successor states of the two left cells are s 1 s 2 in both cases. So, a reverse transition function δ R cannot exist since it must map (s 1 , s 2 ) to s 2 and to s 3 . However, the transitions δ ← (s 1 , s 2 ) = s 1 , δ ← (s 2 , s 2 ) = s 2 , δ ← (s 1 , s 3 ) = s 2 , and δ ← (s 2 , s 3 ) = s 3 do not violate the reversibility of the finite automaton used as single cell.

⊥ a ⊥ a ⊥ a ⊥ b ⊥ b ⊥ b ⊥ b ⊥ b ⊥ b ⊥ b ⊥ b # # 0 a 0 a 0 a 1 b 1 b 1 b 1 b 1 b 1 b 1 b s b # # 0 a 0 a 0 a 1 1 b 1 b 1 b 1 b 1 b 1 b s b s b # # 0 a 0 a 1 a

The Computational Capacity of One-Way Mealy Cellular Automata with Weakly Reversible Cells

Here, we explore the computational capacity of WRC-OMCA. To this end, we start to shed light on the role played by the sink states in such devices.

Lemma 2. Let M be a WRC-OMCA whose cells are reversible disregarding sink states. Then an equivalent WRC-OMCA where all cells are reversible including sink states can effectively be constructed.

Proof. Let M = S, F, A, B, ⊥, #, δ be a WRC-OMCA whose cells are reversible except for sink states (see Figure 3). We consider the state graph of a cell of M . For every sink state s the following steps are repeated. Let G be the part of the graph that does neither include s nor any edge to s. The first step is to remove irreversibility for the edges that enter the sink state from some states in G. To this end, state s is copied as many times as there are incoming edges from states in G. Now these edges are directed to different copies of s.

The next step is to remove the irreversibility caused by the looping edges and the incoming edge from a state in G. To this end, a new copy B = { b | b ∈ B } of B is used. Each edge from a copy of a sink state to itself labeled a, b is relabeled by a, b. The state graph obtained so far is weakly reversible. However, by providing a copy of B the number of messages that may be sent to neighboring cells is increased. Since A = B, additional edges have to be included. To overcome this problem, for every edge in G labeled a, b, an additional edge between the same states labeled ā, b is included in G . Again, this step preserves weak reversibility. Altogether, we have constructed an equivalent WRC-OMCA, since every pair (a, b) from B × B induces an injective partial mapping from the state set S to itself. The idea used to prove Lemma 2 can in fact be generalized. So, it turns out that even WRC-OMCAs have the full computational capacity of OMCAs. Theorem 3. Let M be an OMCA. Then an equivalent WRC-OMCA with all cells reversible including sink states can effectively be constructed.

Reversible One-Way Partitioned Cellular Automata

Now we turn to discuss the details of the definitions in comparison with another related model. In [START_REF] Morita | Language recognition by reversible partitioned cellular automata[END_REF] reversible two-way partitioned cellular automata are studied in terms of language recognition. The important concept of partitioned cellular automata is well-suited to define the notion of reversibility of cellular automata computations. In detail, the cells of a one-way partitioned cellular automaton have partitioned states that is, a state consists of a state part that represents the actual state and a message part the represents the message to be sent to the left neighbor. This message is created by the transition function during a transition. So, as for Mealy cellular automata the transition depends on the current state part and the current message part of its neighbor, and gives the new state part and the message part to be sent to the left, where initially each cell sends a message corresponding to its input symbol and the rightmost cell receives information associated with a boundary symbol on its free input line. So far, Mealy and partitioned cellular automata formalize similar concepts, but in partitioned cellular automata the message to be sent is a part of the state, while in Mealy cellular automata it is not. This makes a difference for reversibility considerations.

Formally, a one-way partitioned cellular automaton (OPCA) is a system S, F, A, #, δ , where S = T × C is the finite, nonempty set of cell states, where T is the message part and C is the state part, F ⊆ S is the set of accepting states, # ∈ T is the distinguished boundary message, A is the nonempty set of input symbols with A ⊆ C and A ⊆ T , and δ : C × T → T × C is the local transition function.

Given some cell state s = (t, c), the projection on its message part t is denoted by π T (s) and the projection on its state part c is denoted by π C (s).

A configuration of a one-way partitioned cellular automaton S, F, A, #, δ is a mapping c : {1, 2, . . . , n} → S, for n ≥ 1, that assigns a state to each cell. The operation starts in a so-called initial configuration, which is defined by the given input w = a 1 a 2 • • • a n ∈ A + . We set c 0 (i) = (a i , a i ), for 1 ≤ i ≤ n. Successor configurations are computed according to the global transition function ∆. Let c be a configuration with n ≥ 1, then the successor configuration c is

c = ∆(c) ⇐⇒ c (i) = δ(π C (c(i)), π T (c(i + 1))), i ∈ {1, 2, . . . , n -1} c (n) = δ(π C (c(n)), #) .
A partitioned cellular automaton is said to be (locally) reversible (REV-OPCA) if and only if its local transition function is injective. So, given a state (s, m) and a transition δ(s, ) = (m , s ), by the injectivity, from (m , s ) the predecessor state s of the cell and the message received in the previous step are uniquely determined. The latter is part of the predecessor state of the right neighbor. In particular, the message part m of the cell cannot be determined. Instead, it is uniquely determined from the left neighbor. So, looking at the whole configuration, the predecessor configuration can be computed. However, the single cell is not necessarily a reversible finite automaton.

In RC-OMCAs the single cells have to be reversible OMCAs. So, for example, transitions δ(s 1 , a 1 ) = (s, b) and δ(s 2 , a 2 ) = (s, b) are allowed, where δ ← (s, a 1 , b) = s 1 and δ ← (s, a 2 , b) = s 2 . These transitions are forbidden in reversible partitioned cellular automata since they violate the injectivity of δ.

The next theorem marks a lower bound for the computational capacity of real-time OPCAs. It says that a real-time OPCA is at least as powerful as a deterministic finite automaton (DFA), where a DFA is a DFMA with a singleton output alphabet, thus, the output is omitted from the transition function. Since it is well known that there are regular languages that are not accepted by reversible DFAs [2,[START_REF] Pin | On reversible automata[END_REF], the next theorem provides a construction of a reversible cellular device that simulates any possibly irreversible regular language. Theorem 4. Let L be a regular language. Then L is accepted by a real-time REV-OPCA.

Proof. Since the regular languages are closed under reversal, we may assume that language L R is accepted by some DFA M with state set S, input alphabet A, initial state s 0 , set of accepting states F , and transition function δ : S × A → S. Moreover, we may assume that the initial state s 0 is left with the very first transition and never reentered.

The idea for the simulation of M by a real-time OPCA M is straightforward. The cells of M run through a loop that keeps their initial states, while at the right end a signal is set up that moves through the array with maximum speed and computes and sends the states of the simulated REV-DFA M . A little extra attention has to be paid for implementing the local transition function of M = S , F , A, #, δ injectively. Depending on M we identify the boundary symbol # of M with the initial state s 0 of M and define # = s 0 , T = S ∪ A, C = A ∪ (S × A), F = {(s, a) ∈ S × A | δ(s, a) ∈ F }, and δ (a, b) = (b, a), for all a, b ∈ A, δ (a, #) = (δ(s 0 , a), (s 0 , a)), for all a ∈ A, δ (a, s) = (δ(s, a), (s, a)), for all a ∈ A and s ∈ S \ {s 0 }, and δ ((s, a), #) = (#, (s, a)), for all (s, a) ∈ S × A (see Figure 4). a 1 a 1 a 2 a 2 a 3 a 3 a 4 a 4 a 5 a 5 # a 2 a 1 a 3 a 2 a 4 a 3 a 5 a 4 s 1 (s0,a5) # a 3 a 1 a 4 a 2 a 5 a 3 s 2 (s1,a4) # (s0,a5) # a 4 a 1 a 5 a 2 s 3 (s2,a3) # (s1,a4) # (s0,a5) # a 5 a 1 s 4 (s3,a2) # (s2,a3) # (s1,a4) # (s0,a5) # s 5 (s4,a1) # (s3,a2) # (s2,a3) # (s1,a4) # (s0,a5) # Fig. 4. A real-time accepting a regular language, where si+1 = δ(si, a5-i), for 0 ≤ i ≤ 4. The input is accepted if δ(s4, a1) = s5 is an accepting state in M .

An inspection of the transition function δ and taking into account that the initial state of M is left in the very first transition and never reentered shows the injectivity of δ . Let the input be a 1 a 2 • • • a n . At time step 1, the rightmost cell n initiates the signal by calculating and sending s 1 = δ(s 0 , a n ). In general, for 0 ≤ i ≤ n -1, the signal reaches cell ni at time i + 1 and calculates and sends state s i+1 = δ(s i , a n-i ). The accepting states of M are defined as those states sending an accepting state of M . So, M accepts L(M ) R = (L R ) R = L.

The next construction shows that real-time REV-OPCAs are also able to accept non-regular context-free languages.

Lemma 5. There is a non-regular context-free language that is accepted by some real-time REV-OPCA.

Proof. We use a language L over alphabet {a, b} * as witness that has the property

L ∩ a * b * = { a m b n | n ≥ m ≥ 1 }.
Since the regular languages are closed under intersection and { a m b n | n ≥ m ≥ 1 } is not regular, L is not regular either.

First, we partially construct a real-time REV-OPCA M = S, F, A, #, δ that accepts inputs from { a m b n | n ≥ m ≥ 1 }. The basic idea is to send a signal with half speed from the rightmost a-cell to the left and a second signal that moves with maximum speed from the rightmost b-cell to the left. Whenever the second signal reaches a cell that already has seen the first signal, the cell enters the accepting state. The crucial point is to implement this behavior with an injective transition function. To this end, we set A = {a, b}, T = {#} ∪ A, C = A ∪ {1, 2}, and F = { (#, 1) }.

General transitions and transitions that implement the half-speed signal are Since the #-signal is transmitted further to the left, one may obtain further accepting computations if the inputs are appropriately extended to the left. However, every input of the form b m a n , for m, n ≥ 1, is rejected, and every input of the form a m b n , for n ≥ m ≥ 1, is accepted. In particular, we derive that L(M ) ∩ a * b * = { a m b n | n ≥ m ≥ 1 }, which shows the lemma.

Conclusions

We have introduced and discussed several notions of local reversibility for realtime OCAs. We have shown that weak reversibility can always be achieved, that is, every possibly irreversible real-time OCA computation can be realized by a real-time OCA composed of weakly reversible components. Concerning the other two notions, namely, strong reversibility and reversible partitioned OCAs we have the conjecture that both models are less powerful. However, both models are still able to accept complex languages such as the non-semilinear language given in Example 1 and the context-free, non-regular language used in Lemma 5. Apart from the question of whether both language classes can be separated from the general model, it would clearly be of interest to identify further language classes which can be accepted by these models. Finally, the strength of a model is to some extent documented by the undecidability of the usually investigated decidability questions such as emptiness, finiteness, inclusion, or equivalence. While all such questions are undecidable for real-time OCAs and hence also for real-time OCAs with weakly reversible cells, nothing is known yet on the status of the decidability questions for real-time OCAs with strongly reversible cells and real-time reversible partitioned OCAs.

  (a,b) : S → S where δ (a,b) (s) = s if and only if b = π B (δ(s, a)) and s = π S (δ(s, a)). In this case, the reverse transition function δ ← : S × A × B → S defined by δ ← (s , a, b) = s if and only if δ(s, a, b) = s induces for every pair (a, b) from A × B a (partial) injective function δ ←

1 b 1 Fig. 2 .

 12 Fig. 2. Space-time diagram of a real-time computation of a one-way Mealy cellular automaton with strongly reversible cells on input a 3 b 8 .

Fig. 3 .

 3 Fig. 3. How to make an automaton with sink state reversible. Automaton G is reversible except for the sink state s, where 0 ≤ i, j ≤ |B| -1 (left). Automaton G is reversible including the two sink states s1 and s2 (right). Every edge in G labeled a, b is labeled a, b and ā, b in G which preserves weak reversibility.

1 .

 1 δ(a, a) = (a, a), 2. δ(b, b) = (b, b), 3. δ(a, b) = (a, 1), and 4. δ(1, b) = (b, 1). The second signal is identified with the message #. It is implemented by 5. δ(b, #) = (#, b), 6. δ(a, #) = (#, a), and 7. δ(1, #) = (#, 1). By inspection of the right-hand sides of the transition function it is evident that δ is injective so far. In order to provide further transition rules for inputs not of the form a m b n , we extend δ injectively by 8. δ(b, a) = (b, 2), 9. δ(2, a) = (a, 2), and 10. δ(2, #) = (#, 2). Now inputs of the form b m a n are treated similarly as inputs of the form a m b n . However, in the b-cells now state parts 2 are used that are not part of accepting states.

Acknowledgments

We greatly acknowledge the valuable comments of the anonymous reviewers which, in particular, helped to improve the result of Theorem 4.


Ville Salo
email: vosalo@utu.fi

Strict asymptotic nilpotency in cellular automata

We discuss the problem of which subshifts support strictly asymptotically nilpotent CA, that is, asymptotically nilpotent CA which are not nilpotent. The author talked about this problem in AUTOMATA and JAC 2012, and this paper discusses the (lack of) progress since. While the problem was already solved in 2012 on a large class of multidimensional SFTs, the full solutions are not known for one-dimensional sofics, multidimensional SFTs, and full shifts on general groups. We believe all of these questions are interesting in their own way, and discuss them in some detail, along with some context.

Introduction

A cellular automaton is nilpotent if every configuration is eventually mapped to the all-zero configuration. This notion is best known as an undecidable property of one-dimensional CA, see [START_REF] Stål | Linear sampling and the ∀∃∀ case of the decision problem[END_REF][START_REF] Kari | The nilpotency problem of one-dimensional cellular automata[END_REF]. Here, we discuss its dynamical aspects. We study the relation of nilpotency and its asymptotic version in the setting of cellular automata on subshifts. Our main point is to state the following questions.

Question 1. Which one-dimensional sofic shifts support cellular automata which are asymptotically nilpotent but not nilpotent? Question 2. Which multidimensional SFTs support cellular automata that are asymptotically nilpotent but not nilpotent? Do any? Question 3. Which full shifts on countable groups support cellular automata that are asymptotically nilpotent but not nilpotent? Do any? Below, these are Question 4, Question 6 and Question 9, respectively. They are discussed in their natural contexts, and we try to include some informal guesses about what the solutions might look like. We also ask other questions, and share some lemmas and examples.

Nilpotency on multidimensional full shifts

We begin with an introduction of the problem and its full solution in the classical multidimensional full shift setting.

Let Σ 0 be a finite alphabet. 1 The d-dimensional full shift is the dynamical system Σ Z d where Z d acts by translations σ v (x) u = x u+v . A cellular automaton is a continuous shift-commuting function f : Σ Z d → Σ Z d . Cellular automata can be characterized concretely as follows: if f is a cellular automaton, then there is a local rule f loc : Σ F → Σ where F ⊂ Z d is a finite neighborhood such that f (x) v = f loc (σ v (x)| F ) for all x ∈ Σ Z d and v ∈ Z d .

A cellular automaton is nilpotent if it is a root of the trivial (constant-zero) cellular automaton, that is, there exists n ∈ N such that f n (x) = 0 Z for all x ∈ Σ Z d .

The second kind of nilpotency we are interested in is asymptotic nilpotency. A cellular automaton is asymptotically nilpotent if every configuration converges to the same point in the limit. More precisely,

∀x ∈ Σ Z d : ∀v ∈ Z d : ∃n 0 ∈ N : ∀n ≥ n 0 : f n (x) v = 0.
Clearly a nilpotent cellular automaton is asymptotically nilpotent. If a cellular automaton is asymptotically nilpotent but not nilpotent, then it is strictly asymptotically nilpotent or SAN. This cannot happen on a d-dimensional full shift:

Theorem 1. A cellular automaton f : Σ Z d → Σ Z d is asymptotically nilpotent if and only if it is nilpotent.
This is proved for d = 1 in [START_REF] Guillon | Asymptotic behavior of dynamical systems and cellular automata[END_REF], and for general d in [START_REF] Salo | On Nilpotency and Asymptotic Nilpotency of Cellular Automata[END_REF]. One might think the proof is direct compactness argument, but in fact the first relies on the geometry of Z and the second on algebraic properties of Z d . We discuss the ideas behind these proofs in Section 6.

Nilpotency from a subset of configurations

In this section, we show examples of how taking our initial configurations from a noncompact set can lead to SAN-like phenomena. These will be used as the basis of constructions in compact settings.

Let f : Σ Z d → Σ Z d be a cellular automaton. Let X ⊂ Σ Z be a subset of Σ Z . We say f is weakly nilpotent on X if and only if ∀x ∈ X : ∃n :

f n (x) = 0, nilpotent on X if and only if f n (X) = {0 Z d } for some n ∈ N, and asymptotically nilpotent on X if f n (x) -→ 0 Z d for all x ∈ X.
If X = Σ Z d , then clearly f is nilpotent (in the sense of the previous section) if and only if it is nilpotent on X (in the sense of this section). It is also known that f is weakly nilpotent on Σ Z d if and only if it is nilpotent on Σ Z d .

We note two trivial examples that are useful to keep in mind:

Example 1 (The shift). Let X ⊂ Σ Z d contain only finite configurations, that is, only configurations x ∈ Σ Z d such that the support supp(x) = {v ∈ Z d | x v = 0}
is finite. Then the shift map σ v (for any nonzero vector v) is asymptotically nilpotent on X, but is weakly nilpotent on X if and only if

X = {0 Z d }.
Example 2 (The spreading state CA). Let S ⊂ Z d be any generating set for the group Z d such that S contains the all-zero vector 0 d ∈ Z d . Consider the CA f with neighborhood S and local rule f loc (P ) = a where a = 0 if P v = 0 for some v ∈ S and a = P 0 d otherwise. Thus, 0 is a spreading state that spreads into every cell that 'sees it'. If a configuration x contains 0, then f is asymptotically nilpotent on {x}, and it is nilpotent on {x} if and only if 0 occurs in a syndetic set, that is, in every translate of a ball of large enough radius. Now the following are easy to see:

f is weakly nilpotent but not nilpotent on the (dense) set of all finite points, f is asymptotically nilpotent on X when X is the (dense) set of generic configurations for some full support ergodic measure µ, but is not weakly nilpotent on this set for any such µ.

The second item is based on the fact that in a generic point for an ergodic measure, we (by definition) see every pattern with the correct frequency, so in particular we see every pattern.

For finite configurations, these trivial examples are sufficient for our purposes, but we note that erasing/eroding finite patterns is a much-studied topic in cellular automata, and there are several interesting constructions and results in this setting. Perhaps the most famous eroder is the GKL automaton [START_REF] Gács | One-dimensional uniform arrays that wash out finite islands[END_REF].

Periodic points are another important non-compact set of starting configurations.

Theorem 2. There is a CA on a one-dimensional full shift which is nilpotent on periodic configurations but is not nilpotent.

The existence of such CA is a direct corollary of the undecidability of nilpotency [START_REF] Stål | Linear sampling and the ∀∃∀ case of the decision problem[END_REF][START_REF] Kari | The nilpotency problem of one-dimensional cellular automata[END_REF], as nilpotency is semi-decidable, and non-nilpotency on periodic configurations is semi-decidable. There are also very simple examples if we consider only periodic configurations whose periods are restricted, and they are actually enough for our application in Section 6: the XOR CA f :

Z Z 2 → Z Z 2 defined by f (x) i = x i + x i+1 (where Z 2 = Z/2Z
) is well-known to be nilpotent on periodic configurations with period of the form 2 n .

Nilpotency on multidimensional subshifts

In the previous section we considered nilpotency when starting from a noncompact set of configurations. Perhaps more natural is to consider the initial set of configurations X to be a subshift, that is, σ v (X) = X for all v ∈ Z d and X is topologically closed, or equivalently X is defined by a set of forbidden patterns.

In this section, we concentrate on the case when X is a subshift and is also closed under f , so that f : X → X is the restriction of a cellular automaton on Σ Z d ; this is the setting of cellular automata on multidimensional subshifts, and such f are precisely the continuous shift-commuting functions on X.

SFTs

First, consider the case d = 1. Let X ⊂ Σ Z be a subshift of finite type or SFT, that is, a closed shift-invariant subset of Σ Z obtained by forbidding a finite set of words. Such X is conjugate2 to the set of paths in a finite graph [START_REF] Lind | An introduction to symbolic dynamics and coding[END_REF]. It is shown in [START_REF] Guillon | Asymptotic behavior of dynamical systems and cellular automata[END_REF][START_REF] Salo | On Nilpotency and Asymptotic Nilpotency of Cellular Automata[END_REF] that in this setting there are no SAN cellular automata.

Theorem 3 (Corollary 1 in [START_REF] Salo | On Nilpotency and Asymptotic Nilpotency of Cellular Automata[END_REF]). Let X ⊂ Σ Z be an SFT. Then a cellular automaton f on X is nilpotent if and only if it is asymptotically nilpotent.

One can try to generalize this to SFTs in higher dimensions. SFTs of Σ Z d are defined like in one dimension, by forbidding finitely many patterns from occurring (and such systems are conjugate to tiling systems induced by finitely many tiles).

Theorem 4 (Theorem 4 in [START_REF] Salo | On Nilpotency and Asymptotic Nilpotency of Cellular Automata[END_REF]). Let X ⊂ Σ Z d be an SFT where finite points are dense. Then a cellular automaton f on X is nilpotent if and only if it is asymptotically nilpotent.

The denseness of finite points is not a property that is often assumed from multidimensional SFTs. A more commonly used gluing property is so-called strong irreducibility. Many other gluing properties have been defined, and some are listed for example in [START_REF] Boyle | Multidimensional sofic shifts without separation and their factors[END_REF]. Definition 1. Let X ⊂ Σ Z d be a subshift. We say X is strongly irreducible if there exists m ∈ N such that for any y, z ∈ X and any finite sets

N, N ⊂ Z d with min{|v-v | | v ∈ N, v ∈ N } ≥ m, there exists a point x ∈ X with x N = y N and x N = z N .
By compactness, the sets N and N can then be taken infinite as well, and we easily obtain the following lemma.

Lemma 1. Let X ⊂ Σ Z d be a strongly irreducible SFT and let x ∈ X. Then the points asymptotic to x are dense in X.

Since a subshift has to have the point 0 Z d in order to support asymptotically nilpotent cellular automata, we see that in our case of interest, strong irreducibility is a stronger requirement than the density of 0-finite points: Corollary 1. Let X ⊂ Σ Z d be a strongly irreducible SFT. Then a cellular automaton f on X is nilpotent if and only if it is asymptotically nilpotent.

I do not know if any such property is required.

Question 4. Is there an SFT X ⊂ Σ Z d for some d ≥ 2 and a CA f : X → X such that f is asymptotically nilpotent but not nilpotent?

If the answer is yes, then the solution would presumably involve constructing an SFT where every configurations sets up some zones where we eventually have only zeroes, in some controlled way. There are many known constructions that might allow this [START_REF] Durand | Fixed-point tile sets and their applications[END_REF][START_REF] Törmä | A uniquely ergodic cellular automaton[END_REF], but since the SFT must be closed under f , this seems difficult.

It is known that the shift is not SAN on any Z 2 -SFT [START_REF] Pavlov | Classification of sofic projective subdynamics of multidimensional shifts of finite type[END_REF][START_REF] Salo | Subshifts with sparse projective subdynamics[END_REF]. In [START_REF] Salo | Subshifts with sparse projective subdynamics[END_REF], this is shown using topological arguments: by passing to a minimal subsystem (in a technical sense) we can always find certain abstract 'spaceships', which prevent nilpotency. The proof is very specific to d = 2, and does not seem to extend to d = 3.

In fact, a cellular automaton on an SFT can be seen as a shift on a higherdimensional SFT by looking at its spacetime diagrams, and thus a positive answer to Question 4 would imply a positive answer to the following (where by the previous paragraph we can just as well restrict to d ≥ 3): Question 5. Is there an SFT X ⊂ Σ Z d for some d ≥ 3 such that X contains at least two points, and σ v is asymptotically nilpotent for some v ∈ Z d ? A shift map is nilpotent on an SFT X (as a cellular automaton) if and only if X = {0 Z d }, so we may replace the assumption that σ v is not nilpotent by the assumption that X has at least two points. The direction v of the shift does not matter, since SFTs are closed under rotating the lattice by elements of GL(n, Z).

Sofics (and beyond)

The proof of Theorem 4 in [START_REF] Salo | On Nilpotency and Asymptotic Nilpotency of Cellular Automata[END_REF] in fact does not require that X is an SFT, but only the property that taking the union of the supports of two configurations of X gives a point in X assuming the supports have large enough distance. This is called zero-gluing in [START_REF] Salo | Subshifts with sparse projective subdynamics[END_REF], where nilpotency is studied in the nondeterministic setting.

SFTs are always zero-gluing, but sofic shifts, which are images of SFTs under cellular automata (which clearly generalizes SFTs), are not. Let us show how the trivial idea of shifting finite points from the last section leads to an equally trivial example of a sofic shift where we can have SAN maps. We remark that sofic shifts on Z are precisely the subshifts whose language is regular, and precisely the subshifts that are defined by a regular language of forbidden words.

Example 3 (One-one). Let Σ = {0, 1} and let X ⊂ Σ Z be defined by the forbidden patterns 10 * 1. This is the one-one subshift. Then X is a countable sofic shift. Then σ is asymptotically nilpotent but not nilpotent on X: on the configuration x i where x i j = 1 ⇐⇒ i = j, the cell at the origin contains 0 after i steps if i ≥ 0, so σ is not nilpotent. However, there can only be one occurrence of 1 in a configuration of X, so σ is asymptotically nilpotent.

If X is sofic and has points with infinite support, then the shift is not SAN (because it is not even asymptotically nilpotent). Using a different CA, there is an example that is topologically transitive, that is for any words u, v that occur in points of X, there exists a word w such that uwv occurs in a point of X.

Example 4. Let Σ = {←, →, 0} and let X be the sofic shift with forbidden patterns the regular language ←0 * ← + →0 * →. Let f be the cellular automaton that moves every ← to the left and every → to the right, removing both on collision. Then f is asymptotically nilpotent but not nilpotent.

Of course, similar examples are obtained on Z d -the one-one example directly generalizes to higher dimensions, and any one-dimensional subshift can be turned into a higher-dimensional one by having an independent copy of it in every Zcoset.

There are also sofic shifts which are not zero-gluing (and thus are in particular not SFTs), but which do not support SAN maps. The following result can be shown with the proof of [START_REF] Guillon | Asymptotic behavior of dynamical systems and cellular automata[END_REF].

Example 5 (The even and odd shifts). Let Σ = {0, 1} and let X ⊂ Σ Z be the subshift with forbidden patterns the regular language 1(00) * 1, and Y ⊂ Σ Z the one with forbidden patterns 10(00) * 1. The subshift X is called the odd shift, and Y the even shift. Both are proper sofic, and neither supports SAN CA.

Intuitively, what is going on is that the even and odd shifts are 'almost' zerogluing, in that two finite configurations can be glued together, up to shifting one of them by one, allowing the same constructions as are used in [START_REF] Guillon | Asymptotic behavior of dynamical systems and cellular automata[END_REF].

Every known one-dimensional sofic shift that does allow SAN maps is based on either the one-one or the idea of colliding particles, and subshifts that are, intuitively, 'almost' of finite type do not support SAN CA. Can one find a characterization of sofic shifts allowing such behavior? Question 6. Let X ⊂ Σ Z be a sofic shift. Under what conditions does there exist a cellular automaton on X which is asymptotically nilpotent but not nilpotent? Question 7. Let X ⊂ Σ Z be a subshift. Are there natural specification, mixing, or gluing properties that forbid the existence of SAN maps X? What properties of X are needed for the proofs of [START_REF] Guillon | Asymptotic behavior of dynamical systems and cellular automata[END_REF][START_REF] Salo | On Nilpotency and Asymptotic Nilpotency of Cellular Automata[END_REF] to go through? Another classification question is which sofic shifts have an undecidable nilpotency problem. In [START_REF] Salo | Computational aspects of cellular automata on countable sofic shifts[END_REF] it is shown that nilpotency is decidable on countable sofic shifts, and we know it is undecidable on full shifts, so this class is something in-between.

Nilpotency as uniform convergence to a point

We now set up a more general framework for nilpotency, so that we do not need to give new definitions every time we generalize our model, and so that we can discuss nilpotency also in positive-dimensional settings.

By definition, a cellular automaton is asymptotically nilpotent if and only if the limit of every point in the action of the CA is the all-zero point. We can characterize nilpotency in terms of this convergence: Lemma 2. Let X ⊂ Σ Z d be any subshift with 0 Z d ∈ X and let f : X → X be a CA. Then f is nilpotent if and only if f n (x) -→ 0 Z d uniformly in x ∈ X.

Inspired by this, we give the following definitions: If (X, f ) is an N-dynamical system (X is a topological space and f : X → X is a continuous function), then we say it is nilpotent, if there is a point 0 ∈ X such that for some n ∈ N, f n (x) = 0 for all x ∈ X, asymptotically nilpotent or AN if there is a point 0 ∈ X such that f n (x) -→ 0 for all x ∈ X, and uniformly asymptotically nilpotent or UAN if this convergence is uniform over X.

We have nilpotent =⇒ UAN =⇒ AN, and we will see these implications are strict in general.

A system is non-uniformly asymptotically nilpotent or NUAN if it is asymptotically nilpotent but not uniformly so, and we define SAN as before as being asymptotically nilpotent but not nilpotent:

SAN = AN ∧ ¬nilpotent, NUAN = AN ∧ ¬UAN

There are many systems that are uniformly asymptotically nilpotent but not nilpotent, even in the zero-dimensional setting, but the previous lemma shows a CA is nilpotent if and only if it is UAN, so a cellular automaton is SAN if and only if it is NUAN. 3 In general, for a dynamical system we can only say NUAN =⇒ SAN.

The questions we are interested in are of the following type: Given a class D of dynamical systems, are there NUAN/SAN systems in D? In this article, we mostly study the case where we fix a dynamical system (a subshift) and let D be its endomorphisms, but we can consider the NUAN/SAN behavior more generally.

We make some basic remarks (see also [START_REF] Guillon | Asymptotic behavior of dynamical systems and cellular automata[END_REF]) and give some examples: A Zsubshift X, seen as an N-system with the action of σ is, by definition, AN if and only if the cellular automaton σ is asymptotically nilpotent on it, and this happens precisely when all points of X contain only zeros in their eventual right tail. Such a subshift is only UAN if and only it is nilpotent if and only if X = {0 Z }. Thus the notions NUAN and SAN agree for Z-subshifts as well.

For an N-subshift X, the characterization of AN is the same. Such X is UAN if and only if it is nilpotent if and only if there is a bound m ∈ N such that x ∈ X =⇒ ∀n ≥ m : x n = 0. These are precisely the N-subshifts which are finite and contain only finite points. Thus the notions NUAN and SAN agree for N-subshifts.

If X ⊂ Σ Z d is a subshift, then a cellular automaton f : X → X is AN if and only if its trace {y ∈ Σ N | ∃x ∈ X : y n = f n (x) 0 d } is AN as a one-dimensional subshift, and f is nilpotent if and only if its trace is.

As we have seen, there are subshifts which are SAN (equivalently NUAN), for example the one-one subshift. The one-sided one-one subshift (the set of right tails of the one from the previous section) can also be described as follows: Let Ṅ = N ∪ {∞} be the one-point compactification of N, with its usual topology. Then the map f defined by

f (n) → n -1 (with ∞ -1 = ∞) for n ≥ 1 and f (0) = ∞ is continuous on Ṅ, and ( Ṅ, f ) is NUAN.
The two-sided one-one subshift can similarly be seen as the subtraction homeomorphism on Ż. There is also a more geometric way to implement this idea: Seeing the circle S 1 as [0, 1] with 0 and 1 identified, the map f (x) = x 2 is welldefined and continuous. In this system (S 1 , f ), every point converges to 0, but this convergence cannot be uniform, as f is a homeomorphism (so every point has a preimage). This example is also NUAN.

The map x → x/2 also gives us continuous dynamics on [0, 1]. This map is not nilpotent, but is UAN. Thus, it is SAN but not NUAN.

Cellular automata on graphs and groups

Next, we generalize in another direction, and replace Z d by a graph.

Let G be any road-colored graph whose edges are colored with colors from a finite set S in such a way that for every vertex v ∈ G, for each s ∈ S there is a unique edge with v as initial vertex and s as label. The terminal vertex of this unique edge is denoted by vs. If u ∈ S * , we write vu

= (• • • ((vu 0 )u 1 ) • • • u |u|-1 ) (with v = v
where is the empty word).

Write Σ G for the set of colorings of the nodes of G. A cellular automaton on Σ G is a function f : Σ G → Σ G such that for some function f loc : Σ F → Σ where F ⊂ S * is finite, we have f (x) v = f loc (a → x va ) for all x ∈ Σ G and a ∈ F .

An important example are cellular automata on groups: Let G be a group generated by a finite set S, and Σ a finite alphabet. Then G acts on Σ G by left translations g • x h = x g -1 h , and continuous functions f : Σ G → Σ G commuting with them are precisely the functions that are cellular automata in the sense of the previous definition on any Cayley graph of G, that is, there always exist

f loc : Σ F → Σ such that f (x) v = f loc (x vs1 , x vs2 , . . . , x vs k )
where s 1 , s 2 , . . . , s k ∈ G. Setting G = Z d , we obtain the classical setting of multidimensional CA. For cellular automata on groups, UAN is equivalent to nilpotency. Thus, in this setting SAN and NUAN are equivalent concepts as well.

One can similarly define cellular automata on monoids: If M is a monoid generated by a set S, then M has right Cayley graph with edges (m, ms) where s ∈ S, and we can consider cellular automata on this graph. Setting M = N, this corresponds to the usual one-sided cellular automata. Example 6. Let f : Σ Z → Σ Z be a cellular automaton which is asymptotically nilpotent on periodic points, but not nilpotent, see Theorem 2. Let C n be the graph with n nodes in a single cycle, with label 1 on each edge. Let G = n C n be a disjoint union of these graphs, and let g : Σ G be the cellular automaton with the same local rule as f . Then clearly g is asymptotically nilpotent. In fact, g is UAN: for every cycle, there is a bounded time after which it contains only zeroes. Nevertheless, g is not nilpotent, as f is not. It follows that this example is not nilpotent, but is UAN. Thus, it is SAN but not NUAN.

Intuitively, this example comes from the fact that the graph is not homogenous, in the sense that the neighborhoods of different nodes look different. If we could 'translate the graph' and take limits of this translation process, we would in a natural sense obtain copies of Z where f is not even asymptotically nilpotent. We do not formalize this idea here.

Example 6 can be seen as a cellular automaton on a group action, as the cellular automaton we define commutes with the action of Z that rotates the information on each C n . We do not formalize this idea either.

While we can have SAN in the setting of CA on graphs (by the previous example), I do not know whether NUAN behavior is possible. Question 8. Is there a road-colored graph G and an alphabet Σ such that some CA f :

Σ G → Σ G is NUAN?
The main question is whether we can obtain SAN maps in the group setting: Question 9. Is there a countable group G and an alphabet Σ such that some CA f : Σ G → Σ G is SAN?

What works on general groups?

Many of the arguments of [START_REF] Guillon | Asymptotic behavior of dynamical systems and cellular automata[END_REF] and [START_REF] Salo | On Nilpotency and Asymptotic Nilpotency of Cellular Automata[END_REF] work on every group, but have only been stated in the Z d case. The first is from [START_REF] Guillon | Asymptotic behavior of dynamical systems and cellular automata[END_REF], and states that there are some patterns that empty a particular cell (or set of cells) forever, in any context. Lemma 3. Suppose G is a countable group and f : Σ G → Σ G is an asymptotically nilpotent CA. Then for every neighborhood V of 0 G there exists a nonempty open set U and n 0 ∈ N such that x ∈ U =⇒ ∀n ≥ n 0 : f n (x) ∈ V .

The second and third lemmas deal with mortal finite configurations. If f : X → X is a CA and x ∈ X, then x is mortal if f is nilpotent on {x}, that is, f n (x) = 0 G for some n ∈ N. The proof of both lemmas below are based on the observation that in an asymptotically nilpotent CA, every cell (or set of cells) must regularly visit the all-zero cylinder.

The second lemma states that if a finite configuration does not spread under an asymptotically nilpotent CA, then it is mortal. Lemma 4. Suppose G is a countable group and f : Σ G → Σ G is an asymptotically nilpotent CA. If x is a finite configuration such that the set {v ∈ G | ∃n :

f n (x) v = 0} is finite, then x is mortal.
The following is proved like Lemma 2 of [START_REF] Salo | On Nilpotency and Asymptotic Nilpotency of Cellular Automata[END_REF]. Lemma 5. Suppose G is a countable group, f : Σ G → Σ G is an asymptotically nilpotent CA and there is a dense set of finite mortal configurations. Then f is nilpotent.

We give an intuitive outline of the proof of the case G = Z of Theorem 1 in [START_REF] Guillon | Asymptotic behavior of dynamical systems and cellular automata[END_REF], highlighting how the geometry of Z is used: Suppose we have an asymptotically nilpotent CA. We use Lemma 3 to get a word w which blocks information flow through its central coordinate. One half of such word (after a few iterations) must then block information flow from one side. Sticking such halves around a finite configuration, the configuration becomes stuck in a finite segment, and it must then be mortal by Lemma 4. This means there is a dense set of mortal finite configurations, and we conclude with Lemma 5. 4In this proof, we make essential use of the fact Z has multiple ends: Cutting w in half effectively splits the group in two, and the CA will never see over the gap. However, everything else follows from general arguments.

In the d ≥ 2 case, the same idea does not work directly, as the blocking words w are replaced by blocking patterns, and they need not block information flow in any essential way. The new idea in [START_REF] Salo | On Nilpotency and Asymptotic Nilpotency of Cellular Automata[END_REF] is that periodizing a point makes the cellular automaton simulate a one-dimensional CA, and we already know the result for such CA. The periodization must be doable in any direction, so we make essential use of the fact that there are quotient maps Z d → Z 'for every dimension d', which is almost the definition of Z d . In this sense, we make essential use of the algebraic structure of Z d .

For some specific groups, it is plausible that SAN behavior can be ruled out easily, by a more assiduous application of these ideas. In the case of free groups (which also have multiple ends), one can directly attempt to mimic the proof of [START_REF] Guillon | Asymptotic behavior of dynamical systems and cellular automata[END_REF], while in the case of the Heisenberg group, one can try to mimic the periodization idea of [START_REF] Salo | On Nilpotency and Asymptotic Nilpotency of Cellular Automata[END_REF].

Conjecture 1. If G is a free group or G is the Heisenberg group, then there are no SAN cellular automata on any full shift on G.

CA with very sparse spacetime diagrams

In this section, we list some results of [START_REF] Törmä | A uniquely ergodic cellular automaton[END_REF]. The construction of [START_REF] Törmä | A uniquely ergodic cellular automaton[END_REF] gives insight into why it is difficult to show that SAN behavior is impossible: we can 'almost' have it on a full shift, in the sense that a non-nilpotent cellular automaton can have both very sparse rows and very sparse columns in the limit.

Consider the full shift Σ Z . Then the Besicovitch pseudometric is defined by

d B (x, y) = lim sup n→∞ 1 2n + 1 |{-n ≤ i ≤ n | x i = y i }|.
Then (Σ Z , d B ) is a topological (non-Hausdorff non-compact) space called the Besicovitch space, and if f : Σ Z → Σ Z is a cellular automaton on Σ Z (in the usual sense), then f is also an endomorphism (continuous shift-commuting self-map) of (Σ Z , d B ). We write d C for the usual metric inducing the product topology on Σ Z . We cite some results of [START_REF] Törmä | A uniquely ergodic cellular automaton[END_REF] about nilpotency on the Besicovitch space.

Proposition 1. Let f : Σ Z → Σ Z be a cellular automaton. Then -f is nilpotent on (Σ Z , d B ) if and only if it is nilpotent on (Σ Z , d C ), and
-if f is AN on (Σ Z , d B ), then it is UAN on (Σ Z , d B ).
These follow from [15, Proposition 41] and [START_REF] Törmä | A uniquely ergodic cellular automaton[END_REF]Lemma 43], respectively. The second item shows that there are no cellular automata that are NUAN over the Besicovitch space.

The main result of [START_REF] Törmä | A uniquely ergodic cellular automaton[END_REF] is the construction of a CA with very sparse spacetime diagrams, and the following is one of the corollaries of the construction: Theorem 5. There is a cellular automaton which is UAN on

(Σ Z , d B ) but is not nilpotent on (Σ Z , d C ).
Thus, there are cellular automata that are SAN over the Besicovitch space. Asymptotic nilpotency for the Besicovitch metric is 'spatial nilpotency', that is, most cells being zero on every row. Thus, to formulate this notion, we need a notion of 'space'. For the temporal direction, we can formulate a notion of nilpotency in density directly: If f : X → X is a dynamical system and 0 ∈ X, then f is asymptotically nilpotent in temporal density or ANTD5 if ∀ > 0 : ∀x ∈ X : lim inf If the convergence is uniform in X for all , we use the obvious acronym UANTD.

Proposition 2. Let f : Σ Z → Σ Z be a cellular automaton. Then f has a unique invariant measure if and only if it is ANTD, and if f is ANTD then it is UANTD.

The first observation is well-known, see [START_REF] Törmä | A uniquely ergodic cellular automaton[END_REF]Proposition 5] for a proof. It is the reason why ANTD cellular automata are usually called uniquely ergodic, since this is the term for having a unique invariant measure in ergodic theory. The second condition says that there are no CA that are 'non-uniformly asymptotically nilpotent in temporal density', and it is also shown in [START_REF] Törmä | A uniquely ergodic cellular automaton[END_REF]Proposition 5].

The construction of [START_REF] Törmä | A uniquely ergodic cellular automaton[END_REF] also gives a CA where the temporal density of zeroes is high: Theorem 6. There exists a cellular automaton f : Σ Z → Σ Z which is ANTD but not nilpotent.

Thus, there are cellular automata that are 'strictly asymptotically nilpotent in temporal density'.

We can formalize the property of [START_REF] Törmä | A uniquely ergodic cellular automaton[END_REF] that the density of zeroes becomes high from every starting configuration also using measures: the CA of [START_REF] Törmä | A uniquely ergodic cellular automaton[END_REF] proving Theorem 5 also has the property that every shift-invariant measure converges to the Dirac measure at zero in the iteration of the CA. In other words, there is a non-nilpotent CA f : Σ Z → Σ Z which, acting over the space of shiftinvariant probability measures on Σ Z , is asymptotically nilpotent toward the Dirac measure at 0 Z .

We mention that for cellular automata, there is also another well-known kind of nilpotency on the space of measures, namely randomization: Example 7. Let f : Z Z 2 → Z Z 2 be the two-neighbor XOR f (x) i = x i + x i+1 . Then f acts on the space of shift-invariant measures M σ on Z Z 2 . It is known that f is randomizing in density [START_REF] Miyamoto | An equilibrium state for a one-dimensional life game[END_REF][START_REF] Lind | Applications of ergodic theory and sofic systems to cellular automata[END_REF][START_REF] Pivato | The ergodic theory of cellular automata[END_REF] in the sense that f n (µ) converges weakly to the uniform Bernoulli measure 'except for a set of times of density zero', whenever µ is a full-support Bernoulli measure. 6 Combining the terminology of Section 3 with that of this section means precisely that f is ANTD on the set of full-support Bernoulli measures, with nilpotency towards the uniform measure.

n→∞ 1 n

 1 |{0 ≤ i < n | d(f i (x), 0) < }| = 1.

Nilpotency discussions are at their clearest when subshifts are pointed, that is, they have a special point 0 Z d as part of their structure, and all nilpotency is toward this special point.

Equal up to shift-commuting homeomorphism.

See, however, Example 6.

As we only want to emphasize what property of Z is used, we are of course omitting some technical details. Interested readers will find the details in the references.

It would be nice to call this just 'asymptotic nilpotency in density', but this is used in[START_REF] Törmä | A uniquely ergodic cellular automaton[END_REF] in the spatial sense.

The initial set of measures can be extended considerably, but we do not know a published reference dealing with a class that is obviously closed under f .

Acknowledgements

We thank Pierre Guillon and Ilkka Törmä for their comments on the draft.


Marcos Roberto Ribeiro
email: marcos.ribeiro@ifmg.edu.br

Maria Camila

N Barioni

Sandra De Amo
email: deamo@ufu.br

Claudia Roncancio

Cyril Labbé
email: cyril.labbe@imag.fr

Soccer2014DS: a dataset containing player events from the 2014 World Cup

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

Introduction

The monitoring of sport players during matches started in the end of XX century [START_REF] Ali | Recording soccer players' heart rates during matches[END_REF]. In this period, the researchers were more concerned to collect just health data from players. Since 2000, the monitoring tasks became more sophisticated due to the development of new technologies for GPS devices and softwares for video processing [Baca et al. 2009, Barris and[START_REF] Barris | A review of vision-based motion analysis in sport[END_REF]. This new technologies allow to collect complex data to be used on detailed analysis of player events.

Despite the players monitoring be very common in official competitions, there are few public datasets with these information available. If we consider the soccer sport, to the best of our knowledge, there exist no public datasets with detailed player events. Thus, our main goal herein is to present the public dataset Soccer2014DS which contains player events of the 2014 Soccer World Cup. This dataset can be useful for diverse research fields such as data mining [Bialkowski et al. 2014, Gyarmati and[START_REF] Gyarmati | Estimating the maximal speed of soccer players on scale[END_REF], sports analytics [START_REF] Lucey | Assessing team strategy using spatiotemporal data[END_REF][START_REF] Perin | Soccerstories: A kick-off for visual soccer analysis[END_REF]] and continuous queries [START_REF] Arasu | STREAM: The Stanford Data Stream Management System[END_REF]].

This paper is organized as follows. Section 2 describes the original extracted data. Next, Section 3 presents the data streams derived from the original data. Section 4 discusses about the research opportunities and Section 5 explains the dataset limitations. Finally, Section 6 concludes the paper.

Data Sources

The creation of the Soccer2014DS dataset started with the extraction of the original data available on the Huffpost Data web site1 [START_REF] Boice | [END_REF]]. This web site contains information about the 2014 Soccer World Cup provided by the company Opta Sports 2 . These data is used to display statistics and graphs about player events. Every match has an individual page where a user can delimit a time-line and see the details of this selection. Our first task was to study the source code of the Huffpost Data web site. Based on this study, we developed a web crawler to extract the data. The crawler starts the extraction in the page of the final match and follows the links to the remaining matches to complete the data collecting.

The extraction of the original raw data was performed in 2015. After this task, we organized the extracted data into the relations Matches, Teams and Players and the stream Events. The relations have just one instance and the duplicated data from all matches was eliminated. On the other hand, the stream Events has 64 instances (one instance per match) preserving all extracted event data. Appendix B presents the logical schema of the dataset (the derived data is addressed in Section 3).

The attributes of the relation Matches are id (match identifier), date, time, venue and attendance. Table 1(a) displays the attributes of the stream Events. The player coordinates (x and y) and final coordinates of the ball (to_x, to_y and to_z) are expressed as a percentage of the field dimensions. The attributes type and outcome are used to identify the move performed by players. Appendix A presents the events associated to every combination of values for these attributes. The attribute field_pass represents the continuous ball possession, t for true and f for false. The attribute side is the field side of the team, H for left side and A for right side. When the move is a pass to another player, the attribute to assumes the identifier of this player. For streams, we also must associate a timestamp for every tuple [START_REF] Arasu | STREAM: The Stanford Data Stream Management System[END_REF], in the stream Events the timestamp is calculated using the attributes min and sec (timestamp = min × 60 + sec). The relation Teams is composed by the attributes id (team identifier), name and iso (ISO acronym).

Derived Streams

After the data extraction described in the previous section, we created derived streams by applying cleaning and conversions over the original data. As described in the previous section, in order to know the exact player move, we must check the attributes type and outcome of the relation Events. In addition, the coordinates of the player and the ball, expressed by float values, could not be suitable for some applications where the user has to indicate a region of the soccer field. To deal with this situation, we decided to create new derived streams: Moves(player_id, place, move) for the performed moves; and Places(player_id, place, ball, direc) for the player positioning. The logical schema presented in Appendix B shows the relationship of the derived streams and the original relations.

The stream Moves contains just the moves performed by the players. So, we do not consider events without ball like cards, substitutions, etc. More precisely, the events types 17,18,19,34,43,58,60, 102 and the events with (type, outcome) equal to (5, 1), (6, 1), (53, 1) and (57, 1) are ignored. For the remaining move types, we use the mapping from (Events.type, Events.outcome) to Moves.move described in Table 3. (1, 0), (2, 1) lbal (lost ball)

(3, 0), (7, 0), (44, 0), (50, 1), (51, 1), (57, 0), (59, 0), (61, 0) drib (dribble)

(3, 1), (42, 1) foul (4, 0) fsuf (foul suffered) (4, 1), (55, 1) dled (dribbled) (45, 0) bout (ball out)

(5, 0), (6, 0) brec (ball recovery) (7, 1), (44, 1), (49, 1), (56, 1), (61, 1) int (interception) (8, 1), (74, 1) gsav (goalkeeper save) (10, 1), (11, 1), (41, 1), (52, 1), (54, 1) clea (clearance) (12, 1) wsho (wrong shot) (13, 1), (14, 1), (15, 1) goal (16, 1) rec (reception) (100, 1) cond (conduction)

(101, 1)

The possible values for the attribute place are defensive area (da), defensive intermediary (di), middle-field (mf), offensive intermediary (oi) and offensive area (oa). Figure 1 displays how we compute these values according to the attribute Events.x represented by dashed lines. The attribute ball (ball possession) is a mapping from the at-tribute field_pass. If field_pass = t then ball = 1, and if field_pass = f then ball = 0. In order to compute de attribute direc (move direction of a player), we consider the previous and the current place of each player. Next, we calculate the horizontal distance (xdist) and vertical distance (ydist) between these places. When ydist = 0 and xdist = 0, the direction is none since the player did not move. If ydist > xdist then the direction is lateral. Otherwise, the direction is backward (for xdist < 0) or forward (for xdist > 0). The full dataset and the importing tool are available for download in a Github repository3 . This repository also provides additional tools for benchmarking continuous queries with temporal conditional preferences. All tools were developed using the python language. The dataset is stored in the directory data. This directory contains the relations Matches, Teams and Players stored in CSV (comma separated values) format. Such relations are the union of the data extracted from all matches. The data directory also contains the subdirectories raw, events, moves and places to store respectively the extracted raw data, the stream Events, the stream Moves and the stream Places.

The subdirectory raw has, for every match, the JSON files match_id.json, match_id-players.json and match_id-teams.json where match_id is the match identifier. The subdirectories events, moves and places contain the CSV files match_id.csv with the stream data of the matches. Table 4 presents the information about tuples and instances for all relations and streams of the dataset. The streams Moves and Places have less tuples than stream the Events due to the data cleaning and the computation of the new attributes.

Data Mining. In the data mining field, our dataset can be explored for the validation of new techniques aiming the detection of temporal patterns and key events. As the dataset has the player coordinates, we can also discover the special relations between this patterns and some specific field regions. Using additional information about the localization of the matches, it could be possible to find player patterns correlated to environmental variables.

Sport Analytics. Our dataset can be used to make various sport analysis over individual players or teams. Using our dataset, specialists are able to analyze the moves performed, the player positioning, pass distances and many others variables related to a specific player. In addition, the information of all team players can be combined to perform analysis over the team strategy and positioning.

Preference Continuous Queries. An interesting research topic in the field of data streams processing is to incorporate temporal conditional preferences into continuous queries [START_REF] Ribeiro | Temporal conditional preference queries on streams[END_REF]. This new kind of query makes use of the implicit temporal information of data streams to select sequences of elements that best fit user preferences. As the tuples of data streams has a timestamp, we can know the order of the tuples. So, by using temporal preferences, the user can express wishes like "if there exists a value X in the past then I prefer a value Y to a value X in the current moment".

Unlike traditional databases, data stream applications do not store all data due to limitations of time and space. The existence of datasets for data streams scenarios are important to allow the validation of new techniques for the evaluation of continuous queries. There are works that proposed synthetic data generators [START_REF] Bifet | MOA: A real-time analytics open source framework[END_REF]], but the real datasets are still useful for many specific situations.

In the work [Ribeiro et al. 2017a] we proposed a preference model for reasoning with temporal conditional preferences on data stream scenarios. The Soccer2014DS dataset was used in the experiments to demonstrate the effectiveness of our proposed approach. We also used the Soccer2014DS dataset in the work [START_REF] Ribeiro | Temporal conditional preference queries on streams[END_REF]. In this latter work, the dataset was used to conduct an extensive set of experiments to compare the performance and the memory usage of algorithms to process continuous queries with temporal conditional preferences.

Limitations

The real soccer datasets collected by Opta Sports have additional information provided by an special attribute (qualifiers). However, these datasets are not public. The extracted data has this attribute, but it has no meaningful values. So, we drop this attribute from our dataset.

Our dataset does not have the coordinates of all players at every second. Only events related to moves, cards, fouls and ball outs were gathered. So, positioning analysis must take this information into consideration.

We calculated just the attributes move, place, ball and direc for the derived streams Moves and Places. Although, new attributes can be computed using the available information in the stream Events, for example, the distance of passes and shots. In addition, we decided to keep each match into an individual stream, but it is possible to join these data into a single stream if it is a requirement of the data analysis task.

Conclusion

In this paper we described the creation of the public dataset Soccer2014DS containing player events of the 2014 Soccer World Cup. The construction of the dataset started with the extraction of data from Internet using a web crawler. This extracted data was used to create the derived data by applying cleaning and conversions techniques.

The dataset and all the developed tools are available for download in a public repository. So, the dataset can be used on the development of new research works related to data mining, sports analytics and continuous queries. We already use the Soc-cer2014DS dataset on our previous works [Ribeiro et al. 2017a[START_REF] Ribeiro | Temporal conditional preference queries on streams[END_REF]] and we are still using this dataset on new researches about continuous queries with temporal conditional preferences.

  Figure 1. Soccer field division

Table 1 . Relation attributes: (a) Events (b) Players

 1

	(a)				(b)
	Attribute	Description		Attribute	Description
	id	Event identifier		id	Player identifier
	period	Period of math		name	Player name
	min, sec	Minute and second	real_position	Detailed position
		of the event		real_position_side Position side
	displaymin	Displayed minute	known_name	Known name
	team	Team identifier		short_name	Short name
	player_id	Player identifier		last_name	Last name
	x, y	Player coordinates	first_name	First name
	type	Type of event (move	middle_name	Middle name
		performed)		team_id	Team identifier
	outcome	Result of the event	preferred_foot	Preferred foot
	field_pass	Continuous	ball	club	Club
		possession		caps	Matches played by player team
	side	Field side of team	goals	Goals
	to_x, to_y, to_z Final coordinates of	jersey_num	Jersey number
		ball		country	Birth country
	to	Player identifier of	birth_date	Birth date
		next move		position	Position

  Table 1(b) presents the attributes of the relation Players. The values for the attributes real_position, real_position_side, preferred_foot and position are shown in Table 2. Please see [Bakker 2015] for more details about the data gathered by the company Opta Sports.

Table 2 . Values for Players attributes

 2

	Attribute	Values
	real_position	Attacking Midfielder, Central Defender, Central Midfielder, Defensive
		Midfielder, Full Back, Goalkeeper, Second Striker, Striker, Wing Back,
		Winger
	real_position_side Centre, Centre/Right, Left, Left/Centre, Left/Centre/Right, Left/Right,
		Right, Unknown
	preferred_foot	Both, Left, Mostly Left, Mostly Right, Right, (empty)
	position	Defender, Forward, Goalkeeper, Midfielder

Table 3 . Move mapping

 3

	move	(type, outcome)
	pass	(1, 1), (59, 1)
	bpas (bad pass)

http://data.huffingtonpost.com/2014/world-cup

http://www.optasports.com/

https://streampref.github.io/wcimport/

Research Opportunities

As we mentioned in the first section, our dataset is useful for a multitude of studies. This section outlines a non-exhaustive list of research fields that can benefit from use our dataset.

Appendix