Martin Kutrib

Andreas Malcher

Matthias Wendlandt

Shrinking One-Way Cellular Automata

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

Introduction

Devices of homogeneous, interconnected, parallel acting automata have widely been investigated from a computational capacity point of view. In particular, many results are known about cellular automata (see, for example, the surveys [START_REF] Kutrib | Cellular automata -a computational point of view[END_REF][START_REF] Kutrib | Cellular automata and language theory[END_REF]) which are linear arrays of identical copies of deterministic finite automata, where the single nodes, which are sometimes called cells, are homogeneously connected to their both immediate neighbors. Additionally, they work synchronously at discrete time steps. The computational power of cellular automata (CA) can be measured by their ability to accept formal languages. Initially, each word is written symbolwise into the cells. Then, the transition function is synchronously applied to each cell at discrete time steps, and the input is accepted if there is a time step at which the leftmost cell enters an accepting state. The in a way simplest model of CA is that of real-time one-way cellular automata (OCA) [START_REF] Dyer | One-way bounded cellular automata[END_REF]. In this model, every cell is connected with its right neighbor only which restricts the flow of information from right to left. Additionally, the available time to accept an input is restricted to the length of the input. The class of languages accepted by real-time OCA is properly included both in the class of languages accepted by real-time CA and by linear-time OCA. Furthermore, it is incomparable with the class of context-free languages. More results on real-time OCA such as, for example, closure properties and decidability questions and references to the literature may be found in [START_REF] Kutrib | Cellular automata -a computational point of view[END_REF][START_REF] Kutrib | Cellular automata and language theory[END_REF].

The first notions of cellular automata date back to Ulam and von Neumann [START_REF] Von Neumann | Theory of Self-Reproducing Automata[END_REF] whose work was biologically motivated by finding a way to design a self-replicating machine. While the birth of new cells and the death of existing cells are natural processes in biology, these features are not reflected, at least to our knowledge and in connection with formal language recognition, in the existing literature. In this paper, we introduce shrinking one-way cellular automata (SOCA). Here, the transition function of each cell is extended so that each cell has the ability to dissolve itself. Dissolving of a cell means that the cell itself and all information stored in the cell is deleted. Moreover, the cell to the left of a dissolved cell is directly connected with the right neighbor of the dissolved cell. In this way, the number of cells available is shrinking. Nevertheless, realtime is still defined by the initial length of the input and the input is accepted whenever the leftmost cell at some computation step enters an accepting state. A related concept is that of fault tolerant CA (see, for example, [START_REF] Harao | Fault tolerant cellular automata[END_REF][START_REF] Kutrib | Space-and time-bounded nondeterminism for cellular automata[END_REF]15,[START_REF] Umeo | A simple design of time-efficient firing squad synchronization algorithms with fault-tolerance[END_REF]). These are CA where cells may become defective, that is, they cannot process the information from its neighbors any longer, but only can forward the unchanged information to its neighbors. Hence, defective cells can no longer take part in the computation, but they are still existing.

The paper is organized as follows. In Section 2 we provide a formal definition of SOCA and an illustrating example. Moreover, real-time SOCA are compared to conventional real-time OCA. To this end, a technique is developed how to embed languages. It turns out that such embeddings of languages are still acceptable by conventional OCA as long as the unembedded language is accepted in time n+r(n), where r is some sublinear function. If the unembedded language is accepted in time 2n, but not in real time, then it is shown that the embedded language is accepted by a real-time SOCA, but not by any real-time OCA. In Section 3 we investigate an interesting relation of real-time SOCA to real-time iterative arrays (IA) which are similar to real-time CA, but process their input sequentially. It is known due to Cole [START_REF] Cole | Real-time computation by n-dimensional iterative arrays of finite-state machines[END_REF] that the language classes induced by real-time IA and real-time OCA are incomparable. Here, we obtain that realtime IA are very close to real-time SOCA. It is shown that for every language L accepted by a real-time IA, a real-time SOCA can effectively be constructed which accepts all words of even or odd length from L, or the language $L R , that is, the reversal of L headed by a new symbol $. In Section 4 we study the relation between the dissolving of cells and additional time. It turns out that real-time SOCA where the number of dissolved cells in accepting computations is bounded by some function r depending on the length of the input, can be simulated by conventional OCA which work in time n + r(n). This enables us to utilize results known for the time hierarchy between real-time and linear-time OCA and to obtain an infinite hierarchy with regard to the number of dissolved cells.

Preliminaries and Definitions

We denote the set of non-negative integers by N. Let A denote a finite set of letters. Then we write A * for the set of all finite words (strings) built with letters from A. The empty word is denoted by λ, the reversal of a word w by w R , and for the length of w we write |w|. For the number of occurrences of a subword x in w we use the notation |w| x . A subset of A * is called a language over A. We use ⊆ for set inclusion and ⊂ for strict set inclusion. For a set S and a symbol a we abbreviatory write S a for S ∪ {a}. We use complexity functions f : N → R + tacitly assuming that the range are integers by setting f (n) = f (n) and denote f also by f . The i-fold composition of a function f is denoted by

f [i] , i ≥ 1. Function f is said to be increasing if m < n implies f (m) ≤ f (n).
The inverse of an increasing and unbounded function f :

N → N is defined as f -1 (n) = min{ m ∈ N | f (m) ≥ n }. The notation f (O(n)) ≤ O(f (n)) means ∀ c ≥ 1 : ∃ n 0 , c ≥ 1 : ∀ n ≥ n 0 : f (c • n) ≤ c • f (n).
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, that is, L \ {λ} = L \ {λ}. Throughout the article two devices are said to be equivalent if and only if they accept the same language.

One-Way (Shrinking) Cellular Automata

A one-way cellular automaton is a linear array of identical deterministic finite state machines, called cells. Except for the rightmost cell each one is connected to its nearest neighbor to the right. The state transition depends on the current state of a cell itself and the current state of its neighbor, where 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. A one-way cellular automaton is said to be shrinking if the cells may dissolve themselves. If a cell dissolves itself the next cell to its left is connected to the next cell to its right. The input mode for cellular automata is called parallel. One can suppose that all cells fetch their input symbol during a pre-initial step. Definition 1. A shrinking one-way cellular automaton (SOCA) is a system S, F, A, #, δ , 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, # / ∈ S is the permanent boundary symbol, and δ : S × S # → S ∪ {dissolve} is the local transition function.

A configuration c t of M at time t ≥ 0 is a string of the form S * #, that reflects the cell states from left to right. The computation starts at time 0 in a so-called initial configuration, which is defined by the

input w = a 1 a 2 • • • a n ∈ A + . We set c 0 = a 1 a 2 • • • a n #. Successor configurations are computed according to the global transition function ∆. Let c t = x 1 x 2 • • • x n #, t ≥ 0, be a configuration, then its successor c t+1 = y 1 y 2 • • • y n # is defined as follows: c t+1 = ∆(c t ) ⇐⇒ y i = h(δ(x i , x i+1 )), i ∈ {1, 2, . . . , n -1} y n = h(δ(x n , #))
where h : S ∪ {dissolve} → S ∪ {λ} is the homomorphism that maps states to states and erases dissolve, that is, h(p) = p for p ∈ S, and h(dissolve) = λ. Thus, ∆ is induced by δ.

• • • a 1 a 2 a 3 a n # Fig. 1.
A (shrinking) one-way cellular automaton.

An SOCA is non-shrinking if δ(s 1 , s 2 ) = dissolve for all s 1 , s 2 ∈ S # . Nonshrinking SOCA are referred to as one-way cellular automata. They are denoted by OCA.

An input w is accepted by an SOCA M if at some time step during the course of its computation the leftmost cell enters an accepting state, that is, the leftmost symbol of the configuration is an accepting state. The language accepted by M is denoted by L(M ). Let t : N → N be a mapping. If all w ∈ L(M ) are accepted with at most t(|w|) time steps, then M is said to be of time complexity t.

In general, the family of languages accepted by some device X with time complexity t is denoted by L t (X). The index is omitted for arbitrary time. Actually, arbitrary time is exponential time due to the space bound. If t is the identity function n, acceptance is said to be in real time and we write L rt (X). The lineartime languages L lt (X) are defined according to

L lt (X) = k∈Q, k≥1 L k•n (X). Example 2. The language L = { $w | w ∈ {a, b} * and |w| a = |w| b } is accepted by a real-time SOCA.
The basic idea to accept language L is that every cell x with x ∈ {a, b} having the border cell as right neighbor sends a signal to the left that eventually dissolves a cell y with y ∈ {a, b} and y = x. Subsequently, this cell dissolves itself in the following step. Meanwhile the signal is forwarded to the left by cells carrying the same input symbol x. Thus, the transition function δ of an SOCA accepting L may be sketched as follows with x ∈ {a, b}. We set δ(x, #) = δ(x , #) = x, δ(x, #) = dissolve, and δ(x, x) = δ(x, x ) = x . If an x-signal reaches a cell carrying an input symbol y ∈ {a, b} with y = x, the cell dissolves itself as well. We set δ(y, x) = δ(y, x ) = dissolve. If the input belongs to L, then all cells carrying a's and b's have been dissolved up to the next to last computation step. Thus, the only $ cell has the border symbol as right neighbor and can enter an accepting state acc. If the only $ cell sees a state x or x to its right, it enters a rejecting state rej. If the input contains no symbol $ at all, then the automaton can never enter an accepting state. If the input contains more than one $, there is a cell having a $-cell as right neighbor. This cell sends a signal to the left that prevents all cells passed through from dissolving and accepting.

To show that the SOCA works in real time, notice that in every second computation step the cell next to the border cell is dissolved. Furthermore, such a cell initiates a signal to the left that will dissolve another cell somewhere to the left. So, at some time step 2i there are i cells dissolved next to the border cell and i signals for dissolving a cell are sent. In particular, for an input word $w with w ∈ L, we have |w| is even and at time 2 |w| 2 exactly |w| 2 cells have been dissolved next to the border cell and exactly |w| 2 cells have been dissolved somewhere to the left. So, only the $-cell at the left border remains which accepts in the next,

t n $ a b b a b b a a # $ a b b a b b a a # $ a b b a b b a ′ # $ a b b a b a # $ a b b a # $ a b b a # $ a b # $ a b # $ # acc # $ b b a a a a # $ b b a a a a # $ b b a a a ′ # $ b b a a ′ a # $ b b a ′ a ′ # $ b a ′ a # $ a ′ # rej a #
Fig. 2. The computation on the left accepts the input $abbabbaa and the computation on the right rejects the input $bbaaaa. Cells to be dissolved in the next time step are depicted with background.

that is, (|w| + 1)st step, hence, in real time. Two example computations can be found in Figure 2.

It is worth mentioning that it is still an open problem whether or not the deterministic context-free language L of Example 2 can be accepted by a realtime OCA.

Does Shrinking Really Help?

It is well known that the family of real-time OCA languages is a proper subfamily of the linear-time OCA languages [START_REF] Kutrib | Cellular automata and language theory[END_REF]. This section is devoted to comparing the power of real-time shrinking one-way cellular automata to the power of classical real-time OCA. It turns out that the former are more powerful.

Let L ⊆ A * be a language and $ / ∈ A be a letter. The embedding of a $ after every symbol from A is given by the homomorphism emb : A * → A * $ , where emb(a) = a$ for a ∈ A. Next we show that this embedding does not help OCA. We consider time complexities from real time to linear time of the form n + r(n), where r : N → N is a linear or sublinear function. In order to avoid functions with strange behavior, we require that r meets the weak properties increasing and r(O(n)) ≤ O(r(n)). Recall that the latter means ∀ c ≥ 1 :

∃ n 0 , c ≥ 1 : ∀ n ≥ n 0 : r(c • n) ≤ c • r(n).
It can easily be verified that many of the commonly considered linear and sublinear time complexity functions have this property. Lemma 3. Let r : N → N be an increasing function so that r(O(n)) ≤ O(r(n)). A language L belongs to the family L n+r(n) (OCA) if and only if emb(L) belongs to L n+r(n) (OCA).

Proof. Let M = S, F, A $ , #, δ be an OCA accepting emb(L) ⊆ A * $ in n + r(n) time. We construct an OCA M = S , F , A, #, δ accepting L ⊆ A * as follows.

The simple basic idea is to let each cell of M simulate two adjacent cells of M , that is, a cell receiving an input from A together with its neighboring cell receiving a $. In each step of M two steps of M are simulated, which is possible since the simulated input of M appears compressed in M . A formal construction is:

S = A ∪ S 2 , F = { (q 1 , q 2 ) ∈ S | q 1 ∈ F }, δ (p 1 , #) = (δ(δ(p 1 , $), δ($, #)), δ(δ($, #), #)) for all p 1 ∈ A, δ (p 1 , q 1 ) = (δ(δ(p 1 , $), δ($, q 1 )), δ(δ($, q 1 ), δ(q 1 , $))) for all p 1 , q 1 ∈ A, δ ((p 1 , p 2 ), (q 1 , q 2 )) = (δ(δ(p 1 , p 2 ), δ(p 2 , q 1 )), δ(δ(p 2 , q 1 ), δ(q 1 , q 2 )))
for all (p 1 , p 2 ), (q 1 , q 2 ) ∈ S 2 , in all other cases δ does not change the current state of a cell. Let w be some word in L. So, M may use 2|w|+r(2|w|) time steps to accept emb(w). In order to complete the simulation on input w, the OCA M takes at most |w| + 1 2 r(2|w|) steps. Since r(O(n)) ≤ O(r(n)), there is a constant c ≥ 1 so that c • r(|w|) ≥ r(2|w|). Therefore, M takes at most |w| + c 2 • r(|w|) steps. Strong speed-up theorems for several devices are obtained in [START_REF] Ibarra | Sequential machine characterizations of trellis and cellular automata and applications[END_REF][START_REF] Ibarra | Some results concerning linear iterative (systolic) arrays[END_REF]. In particular, it is possible to speed up the time beyond real time linearly. Here we choose a speed-up constant 2 c and apply this technique to M . The resulting OCA obeys the time complexity n + r(n) and accepts L.

For the converse simulation, now let M be an n + r(n)-time OCA accepting L ⊆ A * . First, M is sped up to n + 1 2 r(n) time. The further construction idea for an OCA M that accepts emb(L) in n + r(n) time is as follows.

At initial time a signal is sent from the right border to the left. It checks the correct format of the input. If the format is incorrect the left border cell is prevented from accepting. So we safely may assume the format to be correct. All cells remember whether their input symbol is a $ or a symbol from A (the leftmost cell must be an A-cell). Now, in each other time step an A-cell does nothing, while a $-cell copies the current state of its right neighbor as part of its own state. In the following step, a $-cells does nothing, while an A-cell simulates one transition of M .

Let w be some word in L. So, M may use |w|+ 1 2 r(|w|) time steps to accept w. In order to complete the simulation on input emb(w), the OCA M takes at most 2|w| + r(|w|) steps. Since | emb(w)| = 2|w| and r is increasing, this is less than 2|w| + r(2|w|) and M obeys the time complexity n + r(n).

On the other hand, the embedding together with the possibility of cells to dissolve themselves strengthens the power of real-time OCA significantly. As mentioned before, the proper inclusion L rt (OCA) ⊂ L lt (OCA) is known. Lemma 4. Let L be a language from L lt (OCA) \ L rt (OCA). Then emb(L) belongs to L rt (SOCA).

Proof. As in the proof of Lemma 3, we utilize the speed-up techniques obtained in [START_REF] Ibarra | Sequential machine characterizations of trellis and cellular automata and applications[END_REF][START_REF] Ibarra | Some results concerning linear iterative (systolic) arrays[END_REF]. So, we safely may assume that for any linear-time OCA language there exists a (2n -2)-time OCA M that accepts it. Now let L ∈ L lt (OCA)\L rt (OCA). A real-time SOCA M accepting emb(L) works as follows. During the first transition every cell checks whether its right neighbor carries a correct input symbol. That is, a cell with input symbol belonging to the alphabet of L must have a $ neighbor and vice versa (except for the rightmost cell). If the input format is incorrect a failure signal is sent to the left that prevents all cells passed through from dissolving and accepting. During the second transition all cells with $ input dissolve themselves, while the others remain in their states. Finally, the OCA M is simulated on the remaining cells. On input of length n every other cell is dissolved during the first two time steps. Then the simulation of M takes 2 n 2 -2 time steps. Altogether the SOCA M works in n time steps, that is, in real time. Theorem 5. Let L be a language from L lt (OCA) \ L rt (OCA). Then emb(L) belongs to L rt (SOCA) but does not belong to L rt (OCA). In particular, the family L rt (OCA) is properly included in L rt (SOCA).

Real-Time Shrinking OCA and Iterative Arrays

Iterative arrays (IA) are another simple model for massively parallel computations, which sometimes are called cellular automata with sequential input. In connection with formal language processing iterative arrays have been introduced in [START_REF] Cole | Real-time computation by n-dimensional iterative arrays of finite-state machines[END_REF]. What makes these devices interesting in the current context is the incomparability of the families of languages accepted by OCA and IA in real time. Moreover, the latter devices accept non-semilinear unary languages while the former devices accept only regular unary languages. Conversely, for example, all linear context-free languages belong to L rt (OCA) but there is a deterministic linear context-free language not accepted by any real-time iterative array. In the following, we investigate to what extent real-time shrinking OCA can simulate real-time IA.

For the formal constructions we need to introduce IA in more detail. Basically, they are semi-infinite linear arrays of finite automata, again called cells. But now the information flow is two-way, that is, each cell except the leftmost one is connected to its both nearest neighbors (one to the left and one to the right).

s 0 s 0 s 0 s 0 s 0 a 1 a 2 a 3 • • • a n ▽
The input is supplied sequentially to the distinguished communication cell at the origin which connected to its immediate neighbor to the right only. For this reason, we have two different local transition functions. The state transition of all cells but the communication cell depends on the current state of the cell itself and the current states of its both neighbors. The state transition of the communication cell additionally depends on the current input symbol (or if the whole input has been consumed on a special end-of-input symbol). The finite automata work synchronously at discrete time steps. Initially they are in the so-called quiescent state. Definition 6. An iterative array (IA) is a system S, F, A, , s 0 , δ, δ 0 , where S is the finite, nonempty set of cell states, F ⊆ S is the set of accepting states, A is the finite, nonempty set of input symbols, / ∈ A is the end-of-input symbol, s 0 ∈ S is the quiescent state, δ : S 3 → S is the local transition function for non-communication cells satisfying δ(s 0 , s 0 , s 0 ) = s 0 , and δ 0 : A × S 2 → S is the local transition function for the communication cell.

The notions of configurations are a straightforward adaption from OCA. An input is accepted if at some time step during the course of its computation the communication cell enters an accepting state. Acceptance is said to be in real time if all w in the accepted language are accepted within at most |w| + 1 time steps.

The next result reveals an interesting relation between real-time IA and SOCA. The proof shows a basic construction that will later be modified for further relations. Theorem 7. Let L belong to L rt (IA). Then { w | w R ∈ L and |w| is even } is accepted by a real-time SOCA.

Proof. Given a language L accepted by some IA M in real time, the claimed real-time SOCA M is constructed in three steps.

The first step is to embed the computation of M into a one-way device M . To overcome the problem to simulate two-way information flow by one-way information flow, the cells of M collect the information necessary to simulate one transition of M in an intermediate step. So, the first step of M is simulated in the second step of M and so on. Moreover, the configuration flows with speed 1/2 to the left. The behavior is depicted in Figure 4, where for this step it is assumed that the input is available where it is consumed.

The second step is to speed up the computation of M . Assume that in every computation step two input symbols are fed to M . Since all cells of an IA are initially in the same, that is, quiescent state, the computation can be set up such that each cell simulates two cells of M . Hence, this together with the compressed input allows some OCA M to simulate two steps of M at once at every time step. The third step is to construct the desired real-time SOCA M . Based on M we first explain how cells dissolve themselves. This happens at every other time step beginning at time step two. More precisely, all cells maintain an internal counter modulo two. So, they can detect even time steps. At these time steps, precisely the cell which carries two input symbols and whose right neighbor simulates a state of M dissolves itself. Since the simulated configuration flows to the left with speed 1/2 and at every other time step one cell dissolves itself, the cell simulating the communication cell of M arrives at the leftmost cell at real time as desired (see Figure 5). It remains to be shown how the input is provided as requested. To this end, it is sufficient that during the first transition each cell copies the state of its right neighbor, that is its input, as part of its own state.

t n # in s 0 s 0 # s 1,1 s 0 # in s 1,1 s 0 s 0 s 0 # s 1,2 s 2,2 s 0 # in s 1,2 s 2,2 s 2,2 s 0 s 0 s 0 # s 1,3 s 2,3 s 3,3 s 0 # in s 1,3 s 2,3 s 2,3 s 3,3 s 3,3 s 0 s 0 s 0 # s 1,
The SOCA M simulates the given IA M on even length inputs. However, the last step of M depends on the end-of-input symbol. simulate this last step of M . Therefore, the construction has slightly to be extended. Whenever, a cell of M storing input symbols changes to a state that simulates states of M , it simulates one more transition of M under the assumption that the cell has received the last input symbols and, thus, is the leftmost one. The result is stored in an extra register. Finally, a state is accepting if this extra register contains an accepting state of M . The transition that fills the extra register of the real leftmost cell corresponds to the missing last transition of M .

The proof of Theorem 7 can be modified to accept inputs of odd length instead of even length in a straightforward way. Even more complicated cycles of move and dissolve operations can be realized. Example 9. Basically, a function f : N → N is said to be IA-constructible if there is an IA which indicates by states of the communication cell the time steps f (n), for n ≥ 1. For details and further results on IA-constructibility we refer to [START_REF] Buchholz | Some relations between massively parallel arrays[END_REF][START_REF] Fischer | Generation of primes by a one-dimensional real-time iterative array[END_REF][START_REF] Mazoyer | Signals in one-dimensional cellular automata[END_REF]. However, the family of such functions is rich. For example, the functions f (n) = 2 n and f (n) = p n , where p n is the nth prime number, are IA-constructible. Therefore, the non-semilinear unary languages { a 2 n | n ≥ 0 } and { a pn | n ≥ 2 } belong to the family L rt (IA). By Theorems 7 and 8 they are accepted by an SOCA in real time as well. On the other hand, real-time OCA accept only regular, that is, semilinear unary languages [START_REF] Seidel | Language recognition and the synchronization of cellular automata[END_REF].

A further relation between real-time IA and SOCA has been foreshadowed by Example 2. The words of the language of the example have the property that the leftmost cell can identify itself. Clearly this is realized by concatenating a fixed new symbol to the left. In general, we have the following result.

Theorem 10. Let L ⊆ A * be a language from L rt (IA) and $ / ∈ A be a letter. Then { $w | w R ∈ L } is accepted by a real-time SOCA.

Example 11. It is shown in [START_REF] Okhotin | Comparing linear conjunctive languages to subfamilies of the contextfree languages[END_REF] that the real-time deterministic context-free language L = { c m a k0 ba k1 b • • • ba km b • • • ba k bd n | m, n, k i ≥ 0, ≥ 1, k m = n } does not belong to L rt (OCA). Since the family L rt (OCA) is closed under reversal and left quotient with a fixed new symbol, the language $L R does not belong to L rt (OCA), neither. On the other hand, all real-time deterministic context-free languages belong to L rt (IA) [START_REF] Kutrib | Cellular automata and language theory[END_REF]. Now Theorem 10 shows that $L R is accepted by some SOCA in real time.

Dissolving versus Time

In this section, we investigate to what extent the possibility of an SOCA to dissolve cells can be captured by providing additional time. will obtain that this can always be achieved. This result enables us together with a suitable embedding of symbols to translate the time hierarchy known to exist in between real-time and linear-time conventional OCA ( [START_REF] Klein | Fast one-way cellular automata[END_REF]) into a hierarchy for SOCA with regard to the number of cells dissolved. We start by defining classes of SOCA where the maximum number of dissolved cells in accepting computations is put in relation to the length of the input processed.

Let M be an SOCA and f : N → N be an increasing function. If all w ∈ L(M ) are accepted with computations where the number of dissolved cells is bounded by f (|w|), then M is said to be dissolving bounded by f . The class of SOCA that are dissolving bounded by f is denoted by f -SOCA.

The next result says that every dissolving bounded SOCA can be simulated by a conventional OCA with additional time steps depending only on the number of dissolved cells. Theorem 12. Let M be an f -SOCA working in real time. an equivalent conventional OCA M working in time n + f (n) can effectively be constructed.

Lemma 3 and

 3 Lemma 4 have shown the next theorem.

Fig. 3 .

 3 Fig. 3. An iterative array.

Fig. 4 .

 4 Fig. 4. Simulation of two-way information flow by one-way information flow. The input to the OCA is provided at the cells marked by the circled in.

Theorem 8 .

 8 Let L belong to L rt (IA). Then { w | w R ∈ L and |w| is odd } is accepted by a real-time SOCA.

  4 s 2,4 s 3,4 s 4,4 s 0 #

	s 0	s 0	s 0	s 0	s 0
	s 1,1 s 0	s 0	s 0	s 0
	s 1,2 s 2,2 s 0	s 0	s 0
	s 1,3 s 2,3 s 3,3 s 0	s 0
	s 1,4 s 2,4 s 3,4 s 4,4 s 0
			IA		OCA

  1,6 s 2,6 s 3,6 s 4,6 s 5,6 s 6,6 s 0 s 0 s 1,7 s 2,7 s 3,7 s 4,7 s 5,7 s 6,7 s 7,7 s 0 s 1,8 s 2,8 s 3,8 s 4,8 s 5,8 s 6,8 s 7,8 s 8,8

				n
		s 0	s 0	s 0	s 0	s 0	s 0	s 0	s 0	a 1	a 2	a 3	a 4	a 5	a 6	a 7	a 8	#
	t	s 1,1 s 0	s 0	s 0	s 0	s 0	s 0	s 0	a 1 a 2	a 2 a 3	a 3 a 4	a 4 a 5	a 5 a 6	a 6 a 7	a 7 a 8	s 0	#
		s 1,2 s 2,2 s 0	s 0	s 0	s 0	s 0	s 0	a 1 a 2	a 2 a 3	a 3 a 4	a 4 a 5	a 5 a 6	a 6 a 7	s 1-2,2 s 0 , s 0 #
		s 1,3 s 2,3 s 3,3 s 0	s 0	s 0	s 0	s 0		a 1 a 2	a 2 a 3	a 3 a 4	a 4 a 5	a 5 a 6	s 1-2,2 s 0 , s 0	s 0 , s 0 s 0 , s 0 #
		s 1,4 s 2,4 s 3,4 s 4,4 s 0	s 0	s 0	s 0		a 1 a 2	a 2 a 3	a 3 a 4	a 4 a 5	s 1-2,4 s 3-4,4 s 0 , s 0 #
		s 1,5 s 2,5 s 3,5 s 4,5 s 5,5 s 0	s 0	s 0			a 1 a 2	a 2 a 3	a 3 a 4	s 1-2,4 s 3-4,4	s 3-4,4 s 0 , s 0	s 0 , s 0 s 0 , s 0 #
												a 1 a 2	a 2 a 3	s 1-2,6 s 3-4,6 s 5-6,6 s 0 , s 0 #
													a 1 a 2	s 1-2,6 s 3-4,6	s 3-4,6 s 5-6,6	s 5-6,6 s 0 , s 0	s 0 , s 0 s 0 , s 0 #
													s 1-2,8 s 3-4,8 s 5-6,8 s 7-8,8 s 0 , s 0 #
					IA M							SOCA M ′′′
														So far, M does not

s Fig.

5

. Simulation of real-time IA by a real-time on even length input. The internal modulo two counters are not depicted. The red cells dissolve themselves. The state of cell i at time k is denoted by s i,k . We write s i-j,k for s i,k , s i+1,k , . . . , s j,k . The crosshatched cells are those who simulate a further transition under the assumption that they receive the last input symbol.

Next, we utilize results on a time hierarchy in between real-time and lineartime known for OCA to obtain a hierarchy for SOCA according to the number of dissolved cells. The hierarchy result uses the notion of OCA-constructible functions. A function f : N → N with f (n) ≥ n, is OCA-constructible if there exists a length-preserving homomorphism h and a language L ∈ L rt (OCA) such that h(L) = { a f (n)-n b n | n ≥ 1 }. More details on OCA-constructibility may be found in [START_REF] Buchholz | On time computability of functions in one-way cellular automata[END_REF]. Further, the language L d ⊂ {0, 1, (, ), |} + is used whose words are of the form x (

Now, the witness languages for the time hierarchy defined in [START_REF] Klein | Fast one-way cellular automata[END_REF] are as follows. Let f : N → N be an increasing OCA-constructible function and language Lf ⊆ B + be a witness for the constructibility, that is, Lf

From Lf and L d the language L f ⊆ ((A ∪ { }) × B) + is constructed as follows:

1. The second component of each word w in L f is a word of Lf that implies that w is of length f (m) for some m ≥ 1. 2. The first component of w contains exactly f (m)m blank symbols and m non-blank symbols. 3. The non-blank symbols in the first component of w form a word in L d .

Proof. In [START_REF] Klein | Fast one-way cellular automata[END_REF] the proper inclusion L n+r2(n) (OCA) ⊂ L n+r1(n) (OCA) has been shown with L r -1 1 as witness language. Let A be the alphabet of L r -1 1 and M 1 be an (n + r 1 (n))-time OCA accepting L r -1

1

. By applying speed-up techniques we obtain an equivalent OCA M 1 working in time n + r 1 (n) -2.

Here, we will consider language L $,r -1 1 instead, where a word w belongs to L $,r -1

for the homomorphism h(a) = a, for a ∈ A, and h($) = λ. That is, we take the words from L r -1 1 and insert exactly one $ after each of the rightmost r 1 (|w|) symbols.

A real-time r 1 -SOCA M accepting L $,r -1

is constructed as follows. During the first transition, every cell with input from A applies the homomorphism that witnesses the time constructibility of r 1 to the content of its second register and checks whether its right neighbor carries a correct input symbol. That is, if the homomorphic image is a b the cell must have a $ neighbor, if it is an a the cell must not have a $ neighbor. In addition, every cell with input $ must have a neighbor whose homomorphic image is b or the border symbol. If the check fails, a failure signal is sent to the left that prevents all cells passed through from dissolving and accepting. During the second transition all cells with $ input dissolve themselves, while the others remain in their states. Finally, the (n+r 1 (n)-2)-time OCA M 1 accepting L r -1 1 is simulated on the remaining cells. So, the SOCA M accepts an input w if and only if it is of the form A * (A $) * , the input without $ symbols belongs to L r -1

, and the number of $, that is the number of b, is m for input length |w| = r -1 1 (m). The latter means |w| $ = r 1 (|w|). We conclude that M is an r 1 -SOCA that accepts L $,r -1 1 .

In order to derive the time complexity of M , we recall that r 1 (n) are dissolved during the second time step on inputs of length n. Then, the simulation of M 1 on inputs of length nr 1 (n) takes nr 1 (n) + r 1 (nr 1 (n)) -2 ≤ n -2 time steps, since r 1 is increasing. Altogether the r 1 -SOCA M works in n time steps, that is, in real time.

To show a proper inclusion between language classes L rt (r 2 -SOCA) and L rt (r 1 -SOCA), we first notice that the first language class is included in the latter since r 2 •log(r 2 ) ∈ o(r 1 ) holds. Now, we assume by way of contradiction that the language classes L rt (r 2 -SOCA) and L rt (r 1 -SOCA) are identical. Then we obtain that L $,r -1 1 is accepted by some real-time r 2 -SOCA as well. An application of Theorem 12 gives that then L $,r -1 1 also belongs to L n+r2(n) (OCA). So, it remains to be shown that the latter is a contradiction.

The contradiction is derived along the lines of the proof of Lemma 3. Given an

is constructed, such that each cell receiving an input symbol whose homomorphic image is a b simulates two adjacent cells, that is, the cell itself together with its neighboring cell receiving a $. In each such step two original steps are simulated. The rightmost a-cell starts to simulate two steps at time step 1, the next a-cell at time step 2 and so on. In this way, the leftmost cell starts to simulate two steps from time step |w|r 1 (|w|) on.

Let w be some word in L r -1

1

. So, N may use |w| + r 1 (|w|) + r 2 (|w| + r 1 (|w|)) time steps to accept the associated padded word from L $,r -1

1

. In order to complete the simulation on input w, the OCA N takes at most , which is a contradiction.

Example 14. Let 0 ≤ p < q ≤ 1 be two rational numbers. Then there is the following proper inclusion L rt (n p -SOCA) ⊂ L rt (n q -SOCA).

Another example is given by the i-fold iterated logarithms log [i] . Let i < j be two positive integers. Then there is the following proper inclusion L rt (log [j] -SOCA) ⊂ L rt (log [i] -SOCA).


Claudio L M Martins
email: claudio.luis.martins@terra.com.brpedrob@mackenzie.br

Pedro P B De Oliveira

Merging Cellular Automata Rules to Optimise a Solution to the Modulo-n Problem

Keywords: Cellular automata, emergent computation, rule composition, Modulo-n problem, MODn problem, merging, active state transitions, parity problem

Understanding how the composition of cellular automata rules can perform predefined computations can contribute to the general notion of emerging computing by means of locally processing components. In this context, a solution has been recently proposed to the Modulo-n Problem, which is the determination of whether the number of 1-bits in a binary string is perfectly divisible by the positive integer n. Here, we show how to optimise that solution in terms of a reduction of the number of rules required, by means of a merging operation involving of the rules´ active state transitions. The potential for a more general usage of the merging operation is also addressed.

Introduction: The Modulo-n Problem Solution to be Optimised

Cellular automata (CAs) are discrete dynamical systems with a grid-like regular lattice of identical finite automata cells, each cell having an identical pattern of connections to its neighbours. The next state of each cell is given by the transition rule of the automaton, according to the current cell state and those of its neighbouring cells. CAs may perform arbitrary computations, even out of the action of simple local rules [START_REF] Wolfram | A New Kind of Science[END_REF].

One of these computations consists in solving the parity problem, herein denoted the MOD2 problem, which consists of determining the parity of the number of 1s in a binary string: even parity, when the number of 1s modulo-2 is 0, or odd parity, when the number of 1s modulo-2 is 1.

In its formulation for cellular automata, this computational problem is considered solved when any odd-sized (N) binary string initialising a cyclic lattice, is converted, after some time steps, into 0 N or 1 N , if the initial amount of 1-bits is even, or odd, respectively. The MOD2 problem is ill-defined for even-sized lattices because the initial configuration 1 N would have an even number of 1s, which would be a contradiction because 1 N should be the final configuration for lattices with odd number of 1s. Although it has been proved in [START_REF] Betel | Solving the parity problem in onedimensional cellular automata[END_REF] that a one-dimensional rule with radius at least 4 is required to solve MOD2, [START_REF] Martins | Improvement of a result on sequencing elementary cellular automata rules for solving the parity problem[END_REF] and [START_REF] Lee | Parity problem with a cellular automaton solution[END_REF] showed how to solve the problem with a composition of only two elementary rules. This makes it evident the power of rule compositions.

As a general case, we refer to the MODn problem, which consists of determining whether the number of 1-bits in a cyclic binary string is multiple of n, with the constraint that it is always ill-defined for lattice sizes multiple of n.

In [START_REF] Martins | Computing Modulo-n by Composing Cellular Automata Rules[END_REF], we described a generalised solution to the MODn problem, based upon the application of a set of one-dimensional CA rules, in a pre-determined order, which amounts to composing the individual rules employed. This solution is only constrained in that the lattice size N cannot be a multiple of n nor a multiple of any factor of n. Such a general solution (S n ) for the MODn problem, for any binary string  with size N, is given below, where we name rules 0 n R and 1 n R as the Replacement rules, and

0 1 G , 1 1 G , 0 2 G , 1 2
G and so on, as the Grouping rules, whose meanings are defined in the next section.

S n =                                                             n N n N N N n N N N N n n n n R G G R G G E 0 0 1 0 2 1 1 1 1 2 2 2 2 2 2 ... ... 254 . (1)
The solution means that starting with the size-N initial configuration , the following sequence of rule applications should be performed: Since the sequence of rules superscripted with 0 operate on the 0-bits and the ones superscripted with 1 operate on the 1-bits, the stages 1 and 2 above may be inverted, with the same global outcome.

In this paper, we propose a simplification of the solution above, by performing a merging procedure of the rules´ active state transitions, that is, those that replace the state of the centre cell in the neighbourhood.

In the next section, we present the Replacement rules, the Grouping rules and the result of their composition. In Section 3, we discuss the active state transitions of the rules present in S n , as well as how they can be used to simplify their representations.

The merging of these rules is then discussed in Section 4, as well as how the active transitions should be modified so as to render viable mergings. We conclude in Section 5 with various remarks, in particular addressing some conditions we must respect in the choice of rules to be merged and the active transitions to be modified.

Replacement and Grouping Rules

Two key roles are required for rules to solve the MODn problem: to transform certain blocks of states of a configuration, and to group together specific kinds of blocks; these roles are achieved by the Replacement rules (R) and the Grouping rules (G), respectively. Elementary rule 254 just finalises the problem, by preserving the configuration 0 N , and transforming all the others to 1 N .

Replacement rules 0 n R can replace n end 0s, of a sequence of n or more consecu- tives 0s, with n 1s, while, analogously, Replacement rules 1 n R can replace n end 1s, of a sequence of n or more consecutives 1s, with n 0s. Both are, therefore, MODnconserving rules. Considering the n end bits, 0s or 1s, that need to be replaced of a sequence of n or more consecutive identical bits, the following cases are possible: n bits from the left, n-1 from the left and 1 from the right, n-2 from the left and 2 from the right, …, 2 from the left and n-2 from the right, 1 from the left and n-1 from the right, and n bits from the right. Knowing that a one-dimensional CA rule that changes n end bits from one side of the string must have at least radius n, and that it suffices radius n-1 for a rule that is to change n-1 bits from one side and 1 from the other side, or n-2 bits from one side and 2 from the other side, and so on, we can consider only the smallest possible radius of these rules.

So, there are n-1 rules that replace n end 0s, of a sequence of n or more 0s, with n 1s, namely, rule 0 1 , 1  n R (n-1 bits from the left and 1 from the right), that transforms the strings 10 n-1 0 x 01 into 11 n-1 0 x 11, rule 0 2 , 2  n R (n-2 bits from the left and 2 from the right), that transforms the strings 10 n-2 0 x 001 into 11 n-2 0 x 111, and so on, up to rule 0 1 , 1  n R

(1 bit from the left and n-1 from the right), that transforms the strings 100 x 0 n-1 1 into 110 x 1 n-1 1; in all cases, for any integer x ≥ 0.

By applying Replacement rules for   n N iterations, no sequence with n or more consecutive identical bits is left in the lattice, except if its configuration is 0 N or 1 N . In order to eliminate simultaneous occurrence of different blocks of the same bit left by the Replacement rules, the smaller blocks will be grouped into larger ones, moving themselves through the lattice, according to the Grouping rules.

Grouping rules are those that can shift to the left or to the right, strings of m identical bits, in order to group them with larger strings of the same bit. Rules that can only move an isolated bit, 0 or 1 ( 0 1

G or 1 1 G , respectively), should have, at least, radius 2. Rules that can only move an isolated pair of bits should have at least radius 3, and so on. These rules are also MODn-conserving rules.

For either 0 or 1, n-2 Grouping rules will be used, because, after the application of the Replacement rules, no strings of consecutive identical bits larger than n-1 will remain in the lattice. So, we just have to move strings smaller than n-1 consecutive identical bits to group them into the larger blocks of the same bit.

In order to solve the MOD2 problem, since n = 2, no Grouping rules are necessary, as demonstrated in [START_REF] Lee | Parity problem with a cellular automaton solution[END_REF].

By composing only Replacement and Grouping rules, with no application of the elementary rule 254, any initial configuration is transformed into another that belongs to a reduced group of final configurations. We disregard differences due to rotational symmetry, which means that final configurations as 1100000000, 0110000000, ..., 0000000110 are considered the same as 0000000011.

Simplifying the possible relationships between initial and final configurations before applying rule 254, we have the following, where || 1 stands for the number of 1s in string :

If MODn(N) = MODn(|| 1 ) and both ≠ 0 (ill-defined problem): ) or some necklaces

 MODn(|| 1 ) ≠ 0: 1 N (meaning that, when MODn (|| 1 )=1, convergence is to 1 N ) If MODn(N) ≠ MODn(|| 1 ):  MODn(|| 1 ) = 0: 0 N  MODn(|| 1 ) ≠ 0: 0 N-MODn(||1) 1 MODn(||1
We have already disregarded the lattices with size N multiple of n (ill-defined problem), where MODn(N) = 0.

The predominance of 0s instead of 1s is because, at the end, we use the Replacement rules that operate on the 1s, transforming them into 0s.

Necklaces are configurations of the form (0 A 1 B ) C , for integers A, B and C, where A < n and B < n, or A < n and B > n, but B is not multiple of n, or B < n and A > n but A is not multiple of n. For necklace configurations, the Grouping rules just cause shifts on the lattice, with no further effect; also, the Replacement rules cause no effect when A < n and B < n, or may lead to periodic regimes only when A > n or B > n, by continuously transforming (0 A 1 B ) C into (0 A' 1 B' ) C , back and forth.

If N is a prime number, no necklace will remain in the lattice. Therefore, for any initial configurations where MODn(|| 1 ) = 0, the problem is already solved, as defined. However, for all the other configurations where MODn(|| 1 ) ≠ 0 should be converted into 1 N , elementary rule 254 can be used, without affecting the configuration 0 N .

All the details, lemmas and their proofs, and further explanations regarding this section can be found in [START_REF] Martins | Computing Modulo-n by Composing Cellular Automata Rules[END_REF].

Active State Transitions and the Simplified CA Representations

A solution for the MOD3 problem was reported in [START_REF] Xu | Modulo three problem with a cellular automaton solution[END_REF] and further optimised and generalised in [START_REF] Martins | Computing Modulo-n by Composing Cellular Automata Rules[END_REF]. In order to solve the MOD3 problem we need radius 2 rules as Replacement rules and Grouping rules. A radius 2 rule has 32 state transitions that can be active or not: by active transition, we mean those that change the state value of the centre cell of the neighbourhood. CA rules can be represented just through their active transitions, and grouped whenever possible, i.e., placed together at the same row of the state transition table, using symbol * to stand for either possibilities, 0 or 1 (see Figure 1). The written notes indicate which bit is been replaced by the Replacement rule or changed to make the shift by the Grouping rule. The minimum required radius for a rule to perform as expected depends on the number of cells (excluding those with the * character), to the right or to the left, of the centre cell of the neighbourhood of all grouped active transitions. The highest value is the required radius. At the end of Figure 1 we can see that the minimum radius required to both rules is 2.

Transition Transition 31 1 1 1 1 1 31 1 1 1 1 1 1 30 1 1 1 0 1 30 1 1 1 1 0 1 29 1 1 0 1 1 29 1 1 1 0 1 0 1 on the left 28 1 1 0 0 1 28 1 1 1 0 0 1 27 1 1 1 1 0 27 1 1 0 1 1 1 Isolated 0 26 1 1 1 0 0 26 1 1 0 1 0 1 Isolated 0 25 1 1 0 1 0 25 1 1 0 0 1 0 24 1 1 0 0 1 1 st 0 from the left 24 1 1 0 0 0 0 23 1 0 1 1 1 23 1 0 1 1 1 1 22 1 0 1 0 1 22 1 0 1 1 0 1 21 1 0 0 1 1 21 1 0 1 0 1 0 1 on the left 20 1 0 0 0 1 20 1 0 1 0 0 1 19 1 0 1 1 0 19 1 0 0 1 1 0 18 1 0 1 0 0 18 1 0 0 1 0 0 17 1 0 0 1 1 2 nd 0 from the left 17 1 0 0 0 1 0 16 1 0 0 0 1 2 nd 0 from the left 16 1 0 0 0 0 0 15 0 1 1 1 1 15 0 1 1 1 1 1 14 0 1 1 0 1 14 0 1 1 1 0 1 13 0 1 0 1 1 13 0 1 1 0 1 0 1

Merging Replacement and Grouping Rules

The Merging Operation

The merging process should, in fact, be generally regarded as a two-stage process, consisting of joining together the active transitions of the rules involved, with subsequent editing of some of them, if required. Details are given throughout this section.

The Replacement and Grouping rules to be joined in just one Merged rule do not operate on the same strings simultaneously, because these strings have different sizes for any value of n, i.e., while Replacement rules replace n bits (from strings with n or more consecutive identical bits), Grouping rules move m bits (from strings with just an isolated string of m bits), and m is always equal or smaller than n-2.

Therefore, all effects of the Merged rulesuch as the possibility of partition reduction, the formation of strings with only 0s or only 1s, or the formation of some necklacesare the same when applying the separated rules. One exception is the formation of partial necklaces (described in Section 4.2), that occurs because of the impossibility to join some isolated strings to their larger blocks (created by the Grouping rules), due to changes on the lattice, through the simultaneous action of the Replacement and Grouping rules.

As a consequence, the same lemmas and proofs described in [START_REF] Martins | Computing Modulo-n by Composing Cellular Automata Rules[END_REF] should be considered, but the formation of partial necklaces must now be added to the possibilities of final configuration after applying the Merged rule. In the next subsections we address some specific cases, such as the merging of the rules that solve the problem MOD3 and the problem MOD4, so as to convey the underlying issues of the process more clearly.

The MOD3 Case

As is the case here, we may consider that a task of a CA rule can be performed by one or more active state transitions. Accordingly, the task performed by rule 0 1 , 2 Our goal is to ensure that these 3 alternatives can perform the same tasks:

R
N N N R G           0 1 , 2 0 1  , N N N G R           0 1 0 1 , 2  , or N N M           0 1 , 2  .
The application to all possible initial configurations of a given size of the possible rule sequencesthat is, the Replacement rule followed by the Grouping rule, or vice versa, or yet the Merged rule onlyallows us to compare all resulting final configurations; this is what is summarised in Figure 3, for N = 13 (therefore, with respect to all 2 13 different initial configurations).

Analysis of the data in Figure 3 indicates that the Modulo-3 property is preserved for all initial configurations, thus increasing their number of 1s, up to 11, 12 or 13 occurrences, correspondingly to the initial values of Modulo-3 equal to 2, 0 or 1, respectively. This occurs because the Replacement rule can transform three 0s into three 1s. The alternative that begins with the Grouping rule has an advantage in this replacement task, in that it shifts isolated 0s and groups them into larger chains before replacing the 0s. This increases the amount of strings with three or more consecutive 0s, therefore improving the effectiveness of the Replacement rule.

Hence, the final configurations of the different alternatives are not necessarily the same, even disregarding differences due to rotational symmetries, because the number of 1s may be different. Even with the same number of 1s, the spaces between isolated 0s may be also different.

By a superficial analysis, we would say that there is no equivalence among the outcomes of the three possible processing alternatives; but, if we go back to our initial goals, it is possible to observe that, for all possible initial conditions, the application of any of the three alternatives transforms the lattice into a final configuration as desired. In other words, all final configurations have at most two consecutive 0s (because of the Replacement rule) and there are no isolated 0s and isolated pairs of 0s occurring simultaneously (because of the Grouping rule).

Initial

Amount of 1s Amount of Configurations

Amount of 1s Amount of Configurations

Amount of 1s

Amount of Configurations So, if the desired task is exactly the latter (lattice with at most two consecutive 0s, and without isolated 0s and pairs of 0s simultaneously), the goal has been achieved, demonstrating the equivalence of these alternatives.

N N N R G           0 1 , 2 0 1  N N N G R           0 1 0 1 , 2  N N M           0 1 , 2 
We should remember that the solution to the MOD3 alternates the sequence of rules that operate on the 0s with the sequence of rules that operate on the 1s, alternating the size of the bit strings with only 0s and 1s, until achieving the required condition for elementary rule 254 to finalise the solution. G , the solution S 3 is simplified to Ss 3 , using only three rules, instead of five, as originally (according to [START_REF] Martins | Computing Modulo-n by Composing Cellular Automata Rules[END_REF]):

S 3 =                                               3 3 2 3 2 2 0 0 1 1 1 1 3 3 254 N N N N N N R G R G E  ( 2
)
Ss 3 =                     3 2 0 3 1 3 254 N N N N M M E .
(

) 3
Disregarding the action of elementary rule 254 in the previous expressions, and letting S 3 ' and Ss 3 ' denote the remaining (partial) and simplified (partial) solutions, respectively, Figure 4 compares them, displaying a summary of all final configurations left after applying these two solutions to all possible initial configurations with N=16. The final configuration 1100000000000000 and all its equivalent configurations due to rotational symmetry are considered the same.

Amount of 1s

Final Configuration with some Necklaces

No. Of Configs.

Amount of 1s

Final Configuration with some Necklaces

No. Of Configs.

Amount of 1s

Final Configuration with some Partial Necklaces

No. Of Configs. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21845 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21845 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 19232 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 14576 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 4768 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 2608 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 656 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1568 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 144 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 64 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 64 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 4 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2 16 The simplified partial solution transforms some initial configurations into partial necklaces (i.e, configurations where only a part of it is a necklace), further to the necklaces that already had been transformed by the original partial solution.

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 21845 16 1 1 1 1 1 1 1 1 1 1 1 1 1
Necklaces and partial necklaces appear only when MODn(N) ≠ MODn(|| 1 ); otherwise, the lattice converges to 0 N or 1 N . For the MOD3 problem, necklaces have the forms (01) 8 or (0 2 1 2 ) 4 , and partial necklaces belong to ((0 3 ) + (01) + ) + ; they are trapped in these forms because after 0 3 M has transformed the three 0s into three 1s, only isolated 0s remain, that move synchronously, keeping the form ((1 3 ) + (10) + ) + , until 1 3 M is applied, thus reversing the configuration to ((0 3 ) + (01) + ) + . For both alternatives, original and simplified partial solutions, any initial configurations where MODn(|| 1 ) = 0 converges to 0 N and the problem is already solved, as defined. However, in order for all the other configurations with MODn(|| 1 ) ≠ 0 to end up in 1 N , elementary rule 254 is used, with no effect on the configuration 0 N .

The MOD4 Case and the Problem of Synchronised Displacements

Following the same rationale for merging rules in the optimised MOD3 solution (i.e., merging Replacement and Grouping rules that work on the same bit), in order to optimise the solution to MOD4 we have to merge one Replacement rule with two Grouping rules. For the 0-bit, 0 4

M
0 2 , 2 R 0 1 G  0 2 G  0 2 , 2 R 0 1 G  0 2 G  7 t
          3 0 2 , 2 7 0 1 7 0 2 R G G           0 2 0 1 0 2 , 2 G G R  

Removing and Inserting Active Transitions to Change the Displacement

Step of the Rule Hence, for the efficient merging of these three rules, we have to fix these synchronised movements caused by the Grouping rules. A first idea would be to exchange one of them by a shift to the right, compensating for the current shift to the left. However, looking ahead to the context of the MOD5 problem, in order to optimise its solution with 3 Grouping rules, this method would no longer be sufficient.

Since we are handling larger radius than in the MOD3 problem, a more robust solution is to change the displacement step of rule 0 1 G  : instead of moving the isolated 0 just one position to the left, we had better move it two positions, whenever possible (which is not always the case). The new rule with this feature is denoted

Removing Active State Transitions to Eliminate Remaining Synchronised Displacements

Finally, there is a further problem yet to be solved: when the isolated 0 cannot be moved 2 positions because of an isolated pair of 0s close to its left (as happens in the string *100101*), a synchronised displacement will continue to occur. Therefore, instead of transforming the string 100101 into 001011 (as would happen due to the modification just proposed), we had rather transform it into 000111.

To accomplish this some active state transitions should be turned off, as shown in Figure 7, indicated by two arrows. For clarity purposes of this process, notice that the string **0101* in Figure 6 The ideal merging of active state transitions to solve these conflicts is presented in Figure 8.

: S 4 =       2 254 N E                                                     4 4 2 2 4 2 2 0 0 1 0 2 1 1 1 1 2 4 4 N N N N N N N R G G R G G  (4) Ss 4 =       2 254 N E               4 0 1 4 4 N N N M M . (5)
Testing the same procedure for MOD5 and obtaining similar results, we conclude that the simplified solution that can solve the MODn problem can have only 3 rules, one elementary (radius 1), and two others with radius n-1, as long as the size N of the binary string  is not multiple of n neither multiple of any factor of n. This simplified solution then becomes:

Ss n =       2 254 N E               n N N N n n M M 0 1 . (6)

Concluding Remarks

We demonstrated how a simple action, locally coordinated, represented here by one-dimensional cellular automata rules, can perform a solution to a complex global computation such as the MODn problem.

The design of rules to compute some task may start from analysing these tasks, and maybe dividing them into smaller instances. For each minor task, we can select a single or a group of active state transitions to execute it.

Different tasks performed by different CA rules, can be merged in a single rule, as long as there is no conflict among the individual tasks; this was the case of the task performed by the Replacement rules and the one performed by the Grouping rules in the MOD3 problem.

Much study is still necessary for the understanding and the generalisation of these mergings. However, in our work we could realise some evidence which might help further studies.

Rules classified with fixed point or null dynamical regimes according to [START_REF] Li | Parameterizations of Cellular Automata Rule Space[END_REF] yield a predictable behaviour and render themselves, in some cases, to performing specific tasks. These rules are good candidates to have their active transitions joined or even separated, generating other rules that perform the same task. In contrast, rules with complex, chaotic or periodic dynamical behaviours are not candidates for these compositions or decompositions of their active transitions.

Even for the candidate rules, it is not always possible to merge their tasks into a single rule, especially when there is an overlap among the active transitions, or when two tasks performed simultaneously do not perform as required; this is what occurred, for instance, in our attempt to join the two Grouping rules, where one of them grouped isolated bits and the other grouped isolated pairs of bits in the MOD4 problem.

In order to merge rules for performing equivalent operation, we modified tasks and solved conflicts, following a standard that allowed us to generalise the MODn solution. As n increases, in order to solve the MOD5 problem, for instance, the number of synchronised displacements caused by merging Grouping rules also increases. For the suitability of 0 5 M and 1 5 M , we then have to disable 5 pairs of groups of active transitions. In general, this number depends on n, as exemplified in Figure 9. The number of pairs of groups of active transitions to be disabled for each merging rule is C n-2,2 + 2C n-3,2 + 3C n-4,2 + … + (n-3)C 2,2 which can be calculated through the 4th degree polynomial ((n-3) 4 + 6(n-3) 3 + 11(n-3) 2 + 6(n-3))/24. All these conflicts can be eliminated, and the merging process can always be carried out.

G 3* G 2* G 2* G 4* G 3* G 2* G 3* G 2* G 2* G 5* G 4* G 3* G 2* G 4* G 3* G 2* G 3* G 2* G 2* G 4* 1 G 3* 1 G 3* 1 1 1 G 2* 1 G 2* 1 1 1 G 2* 1 1 1 1 1 1 G 1* 1 1 1 G 1* 1 1 1 1 1 G 1* 1 1 1 1 1 1 1 1 1 1 G 3* 1 G 2* 1 1 G 2* 1 1 1 G 1* 1 G 1* 1 1 1 G 1* 1 1 1 1 1 1 G 2* 1 G 1* 1 G 1*

4 . 2 N

 42 Finalise the process, by applying elementary CA rule 254 for   time steps.

We refer to a

  Grouping rule that can shift m 0s as 0 m G ; but since this movement may be possible to the left or to the right, we denote it 0 is to the right. Analogously, in order to shift and group m 1s,

Figure 1 :

 1 Figure 1: State transitions of rules 0 1 , 2 R and 0 1 G 

2 R

 2 This figure shows all the state transitions of the rules 0 placing together only the active transitions as shown further down in the figure.The Replacement rule 0 1 , has only 6 active transitions, highlighted out of the 32 possibilities, and can be represented by the three rows and the end of the figure. The Grouping rule 0 1 G  has 8 active transitions, and can be represented just by two rows.

  , for example, is to eliminate any string with three or more consecutive 0s in the lattice, conserving the Modulo-3 property, while the task performed by the rule 0 1 G  is to shift isolated 0s to the left in order to group them with larger strings of the same bit, also conserving the Modulo-3 property. In what follows, we go about joining these functions into a single rule.

Figure 1 Figure 2 :

 12 Figure 1 shows that Replacement rule 0 1 , 2 R and Grouping rule 0 1 G 

Figure 3 :

 3 Figure 3: Summary after the application to all possible initial configurations of a given size (N=13) of the different rule sequences.

Therefore, applying rule 0 3 M instead of 0 3 R and 0 1 G , and rule 1 3

 3311

Figure 4 :

 4 Figure 4: Summary after applying both partial solutions (original and simplified) to the MOD3 problem on all possible initial configurations of size 16.

2 G 1 G and 0 2 G

 212 should have radius 3, at least. Therefore, the resulting 4 M rules should also have radius 3. We employ the '+' symbol for the joining of active transitions of the rules.The problem in this merging is related to the Grouping rules. For instance, applying rules 0 , separately or joined, without editing some active transitions, does not lead to the same outcome because of possible synchronised movements of isolated 0s and isolated pairs of 0s.

Figure 5

 5 Figure 5 shows the joining of rules 0 2 , 2 R , 0 1 G 

Figure 5 :

 5 Figure 5: Joining of rules 0 2 , 2 R , 0 1 G  and 0 2 G 

  Figure 6: Rule 2 , 0 1 G 

Figure 7

 7 Figure 7). Rule 0 2 , 2 M 



  Figure 7: Rules 2 , 0 1 G 

G

  , we have to disable active transitions in the rule pairs involved in synchronised displacements of strings, as shown below (where  G stands for either 0

Figure 9 :

 9 Figure 9: Number of groups of active state transitions to be disabled according to n.

Acknowledgements:

We are grateful to CNPq -Conselho Nacional de Desenvolvimento Científico e Tecnológico, and IPM -Instituto Presbiteriano Mackenzie.


Abhijin Adiga
email: abhijin@vbi.vt.edu

Hilton Galyean
email: hgalyean@vt.edu

Chris J Kuhlman
email: ckuhlman@vbi.vt.edu

Michael Levet
email: mlevet@vt.edu

Henning S Mortveit
email: henning.mortveit@vbi.vt.edu

Sichao Wu
email: sichao@vbi.vt.edu

Network Structure and Activity in Boolean Networks

Keywords: Boolean networks, finite dynamical system, activity, sensitivity, network, sensitive dependence on initial conditions, 4

de documents scientifiques 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

A Boolean network (BN) is a map of the form

F = (f 1 , . . . , f n ) : {0, 1} n -→ {0, 1} n . (1)
BNs were originally proposed as a model for many biological phenomena [START_REF] Kauffman | Metabolic stability and epigenesis in randomly constructed genetic nets[END_REF][START_REF] Kauffman | The origins of order: Self-organization and selection in evolution[END_REF], but have now been used to capture and analyze a range of complex systems and their dynamics [START_REF] Aldana | Boolean dynamics with random couplings[END_REF]. Associated to F we have the dependency graph of F whose vertex set is {1, 2, . . . , n} and with edges all (i, j) for which the function f i depends non-trivially on the variable x j . See [START_REF] Goles | Neural and Automata Networks: Dynamical Behaviour and Applications[END_REF][START_REF] Robert | Discrete Iterations. A Metric Study[END_REF][START_REF] Mortveit | An Introduction to Sequential Dynamical Systems[END_REF] for more general discussions of maps F .

The study of stability and the response to perturbations of Boolean networks is central to increased understanding of their dynamical properties. Perturbations may take many forms, with examples including perturbations of the dependency graph [START_REF] Adiga | Sensitivity of diffusion dynamics to network uncertainty[END_REF][START_REF] Luo | Evolving sensitivity balances boolean networks[END_REF][START_REF] Pomerance | The effect of network topology on the stability of discrete state models of genetic control[END_REF], the vertex states [START_REF] Shmulevich | Activities and sensitivities in Boolean network models[END_REF][START_REF] Ghanbarnejad | Impact of individual nodes in boolean network dynamics[END_REF][START_REF] Serra | On the dynamics of random boolean networks subject to noise: attractors, ergodic sets and cell types[END_REF], the vertex functions [START_REF] Shmulevich | The role of certain post classes in boolean network models of genetic networks[END_REF][START_REF] Xiao | The impact of function perturbations in boolean networks[END_REF], or combinations of these.

This paper is concerned with noise applied to vertex states. Specifically, we want to know the following:

What is the probability that F (x) and F (x + e i ) are different?

Here i is a vertex while e i is the i th unit vector with the usual addition modulo 2. In [START_REF] Shmulevich | Activities and sensitivities in Boolean network models[END_REF], Shmulevich and Kauffman considered Boolean networks over regular graphs with f j = f for all vertices j, that is, a common vertex function. They defined the notion of activity of f with respect to its i th argument as the expected value of the Boolean derivative of f with respect to its i th variable. Under their assumptions, this may give a reasonable indication of the expected impact of perturbations to the i th variable under the evolution of F . However, this approach does not consider the impact of the dependency graph structure. We remark that Layne et al. compute the activities of nested canalyzing functions given their canalyzing depth, extending results in [START_REF] Shmulevich | Activities and sensitivities in Boolean network models[END_REF] on canalyzing functions, see [START_REF] Layne | Nested canalyzing depth and network stability[END_REF],

This question of sensitivity has also been studied when x is restricted to attractors in order to assess stability of long-term dynamics under state noise. The notion of threshold ergodic sets (TESs) is introduced in [START_REF] Ribeiro | Noisy attractors and ergodic sets in models of gene regulatory networks[END_REF] and studied further in [START_REF] Luo | Evolving sensitivity balances boolean networks[END_REF][START_REF] Kuhlman | Attractor stability in nonuniform boolean networks[END_REF]. The structure of TESs capture long-term stability under state perturbations of periodic orbits and the resulting mixing between attractors that may happen as a result.

Other tools for analyzing sensitivity of vertex noise includes Lyapunov exponents, see for example [START_REF] Baetens | Phenomenological study of irregular cellular automata based on lyapunov exponents and jacobians[END_REF][START_REF] Baetens | Effect of asynchronous updating on the stability of cellular automata[END_REF], although this is perhaps mostly relevant or suited for the infinite case such as cellular automata over (infinite) regular lattices. Also, the notion of Derrida diagrams have been used to quantify how Hamming classes of states separate on average [START_REF] Derrida | Random networks of automata: A simple annealed approximation[END_REF][START_REF] Fretter | Perturbation propagation in random and evolved boolean networks[END_REF] after one or k transitions under F . Derrida diagrams, however, are mainly analyzed through numerical experiments via sampling. Moreover, analyzing how Hamming classes of large distance separate under F may not be so insightful -it seems more relevant to limit oneself to the case of nearby classes of vertex states.

Returning to the original question, we note that F (x) and F (x + e i ) may only differ in the coordinates j for which f j depends on x i . The answer to the question therefore depends on the vertex functions in the 1-neighborhood of i in the dependency graph X, and therefore the structure of the induced subgraph of the 2-neighborhood of i in X with the omission of edges connecting pairs of vertices both of distance 2 from i. We denote this subgraph by X(i; 2), see Figure 1.

To determine the activity of vertex i one will in general have to evaluate F over all possible states of X(i; 2), a problem which, in the general case, is computationally intractable. We will address three cases in this paper: the first case is when X(i; 2) is a tree, the second case is that of elementary cellular automata (a special case of the former case), and the case where X is a regular, square, 2-dimensional lattice. Work for other graph classes is in progress and we comment on some of the challenges in the Summary section. Here we remark that a major source of challenges for analytic computations is the introduction of type-3 and type-4 edges as illustrated in Figure 1. Lack of symmetry adds additional challenges. The activity of a vertex can be evaluated analytically using the inclusion-exclusion principle, and type-3 and type-4 edges impact the complexity of the combinatorics.

Girth-4 edge

Fig. 1. The subgraph X(i; 2) of X induced by vertex i and its distance 2 neighbors. Vertices belonging to the closed 1-neighborhood n[i] of i are marked red. Type-3 edges (relative to i) connect neighbors of i, while type-4 edges connect neighbors of j ∈ n [i] through a common neighbor different from i. Here n [i] is n[i] with i omitted. Edges connecting vertices of distance 2 from i in X do not belong to X(i; 2). For terminology we refer to Section 2.

A goal of the work on activity started here is as follows: when given a network X and vertex functions (f i ) i , we would like to rank the vertices by activity in decreasing order. Just being able to identify for example the ten (say) vertices of highest activity would also be very useful. This information would allow one to identify the vertices for which state perturbations are most likely to produce different outcomes, at least in the short term. In a biological experiment for which there is a BN model of the form (1), one may then be able to allocate more resources to the measurement of such states, or perhaps ensure that these states are carefully controlled and locked at their intended values.

Paper organization. After basic definitions and terminology in Section 2 we carefully define a new notion of activity denoted by ᾱF,i . Basic results to help in analytic evaluations of ᾱF,i are given in Section 3 followed by specific results for the elementary cellular automata in Section 4, d-regular trees in Section 5, and then nor-BNs over square lattices in Section 6. A central goal is to relate the structure of X(i; 2) and the functions (f j ) j to ᾱF,i . We conclude with open questions and possible directions for followup work in Section 7.

Background, Definitions and Terminology

In this paper we consider the discrete dynamical systems of the form (1) where each map f i is of the form f i : {0, 1} n -→ {0, 1}. However, f i will in general depend nontrivially only on some subset of the variables x 1 , x 2 , . . ., x n , a fact that is captured by the dependency graph defined in the introduction and denoted by X F or simply X when F is implied. The graph X is generally directed and will contain loops. We will, however, limit ourselves to undirected graphs.

Each vertex i has a vertex state x i ∈ {0, 1} and a vertex function of the form f i : {0, 1} d(i)+1 -→ {0, 1} taking as arguments the states of vertices in the 1-neighborhood of i in X. Here d(i) is the degree of vertex i. We write n[i] for the ordered sequence of vertices contained in the 1-neighborhood of i (with i included) and x[i] for the corresponding sequence of vertex states. We denote the system state by x = (x 1 , . . . , x n ) ∈ {0, 1} n .

We will write the evaluation of F in (1) as

F (x) = f 1 (x[1]), f 2 (x[2]), . . . , f n (x[n]) .
The phase space of the map F in ( 1) is the directed graph Γ (F ) with vertex set {0, 1} n and directed edges all pairs (x, F (x)). A state on a cycle in Γ (F ) is called a periodic point and a state on a cycle of length one is a fixed point. The sets of all such points are denoted by Per(F ) and Fix(F ) respectively. All other states are transient states. Since {0, 1} n is finite, the phase space of F consists of a collection of oriented cycles (called periodic orbits), possibly with directed trees attached at states contained on cycles.

In this paper we analyze short-term stability of dynamics through the function α F,i : K n -→ {0, 1} defined by

α F,i (x) = I[F (x + e i ) = F (x)] ( 2
)
where I is the indicator function and e i is the i th unit vector. In other words, α F,i (x) measures if perturbing x by e i results in a different successor state under F than F (x).

Definition 1. The activity of F with respect to vertex i is the expectation value of α F,i using the uniform measure on K n :

ᾱF,i = E[α F,i ] . (3)
The activity of F is the vector

ᾱF = (ᾱ F,1 , ᾱF,2 , . . . , ᾱF,n ) , (4)
while the sensitivity of F is the average activity ᾱ = n i=1 ᾱF,i n .

For a randomly chosen state x ∈ K n , the value ᾱF,i may be interpreted as the probability that perturbing x i will cause F (x + e i ) = F (x) to hold. This activity notion may naturally be regarded as a measure of sensitivity with respect to initial conditions. From (2) it is clear that ᾱF,i depends on the functions f j with j ∈ n[i] and the structure of the distance-2 subgraph X(i; 2), see Figure 1. The literature (see, e.g. [START_REF] Shmulevich | Activities and sensitivities in Boolean network models[END_REF][START_REF] Layne | Nested canalyzing depth and network stability[END_REF]) has focused on a very special case when considering activity. Rather than considering the general case and Equation ( 2), they have focused on the case where X is a regular graph where each vertex has degree d and all vertices share a common vertex function f : K d -→ K. In this setting, activity is defined with respect to f and its i th argument, that is, as the expectation value of the function I[f (x + e i ) = f (x)] where x ∈ K d+1 . Clearly, this measure of activity is always less than or equal to E[α F,i ]. Again, we note that this simpler notion of activity does not account for the network structure of X(i; 2).

Preliminary Results

For the evaluation of ᾱF,i we introduce some notation. In the following we set K = {0, 1}, write N i for the size of X(i; 2), and

K(i) = K Ni for the projection of K n onto the set of vertex states associated to X(i; 2). For j ∈ n[i], define the sets A j (i) ⊂ K(i) by A j (i) = {x ∈ K(i) | F (x + e i ) j = F (x) j } .
These sets appear in the evaluation of ᾱF,i , see Proposition 2. For convenience, we also set A m j (i) = {x ∈ A j (i) | x i = m} , for m = 0, 1. We write Āj (i) = A 0 j (i) and n k for binomial coefficients using the convention that it evaluates to zero if either k < 0 or n -k < 0.

The following proposition provides a somewhat simplified approach for evaluating ᾱF,i in the general case. Proposition 2. Let X be a graph and F a map over X as in [START_REF] Adiga | Sensitivity of diffusion dynamics to network uncertainty[END_REF]. The activity of F with respect to vertex i is

ᾱF,i = Pr j∈n[i] A j | x i = 0 = Pr j∈n[i] Āj . (5)
Proof. As stated earlier, we can write

ᾱF,i = E[α F,i ] = x∈K n α F,i (x)Pr(x) = x∈K(i) α F,i (x)Pr(x) = Pr j∈n[i] A j ,
where probabilities in the first and second sum are in K n and K(i), respectively. This follows by considering the relevant cylinder sets. Equation ( 5) follows by conditioning on the possible states for x i . Since we are in the Boolean case, we have a bijection between each pair of sets A 0 j and A 1 j for j ∈ n[i] which immediately allows us to deduce Equation (5).

As an example, consider the complete graph X = K n with threshold functions at every vertex. Recall that the standard Boolean threshold function, denoted by τ k,n : K n -→ K, is defined by

τ k,n (x 1 , . . . , x n ) = 1, if n j=1 x j k, 0, otherwise. (6)
Here we have

ᾱF,i = n -1 k -1 2 n-1 .
To see this, note first that all the sets Āj (i) are identical. For a state x with x i = 0 to satisfy τ k (x) = τ k (x + e i ) it is necessary and sufficient that x belong to Hamming class k-1. Since x i = 0, it follows from Proposition 2 that Pr( Āj (i)) =

1 2 n-1 A j = n-1 k-1
2 n-1 as stated. Next, consider the Boolean nor-function nor m : K m -→ K defined by

nor m (x 1 , . . . , x m ) = (1 + x 1 ) • • • • • (1 + x m ) , (7)
with arithmetic operations modulo 2. If we use the nor-function over K n we obtain

ᾱF,i = 1/2 n-1 .
Again, Āj = Āk for all j, k ∈ n[i] and we have F (x + e i ) i = F (x) i precisely when x j = 0 for all j ∈ n(i) leading to Pr Āi = 1 2 n-1 . We record the previous two results as a proposition: Proposition 3. If F is the GDS map induced by the nor-function over K n , then

- α F,i = 1 2 n-1 ,
and if F is induced by the k-threshold function over K n , then

ᾱF,i = n -1 k -1 2 n-1 .
In the computations to follow, we will frequently need to evaluate the probability of the union of the A j 's. For this, let B denote the union of A j 's for all j = i. We then have Pr

j∈n[i] A j = Pr(A i ∪ B) = Pr(B) + Pr(A i ∩ B c ) = 1 -Pr(B c ) + Pr(A i ∩ B c ) , (8)
where B c denotes the complement of B.

Activity of Elementary Cellular Automata

The evaluation of Equation ( 5) can often be done through the inclusion-exclusion principle. We demonstrate this in the context of elementary cellular automata (ECA). This also makes it clear how the structure of X comes into play for the evaluation of ᾱF,i .

Let F be the ECA map over X = Circle n with vertex functions given by f : {0, 1} 3 -→ {0, 1}. We will assume that n 5; the case n = 3 corresponds to the complete graph K 3 and the case n = 4 can be done quite easily. Here we have ᾱF,i = Pr Āi-1 (i) ∪ Āi (i) ∪ Āi+1 (i) .

Applying the definitions,

Āj (i) = x = (x i-1 , x i-1 , x i = 0, x i+1 , x i+2 ) | and f x[j] = f (x + e i )[j] (9) for j ∈ n[i] = {i -1, i, i + 1} with indices modulo n. Proposition 4. The activity for k-threshold ECA is ᾱF,i =      0, if k = 0 or k > 3 , 1/2, if k = 1 or k = 3 , 7/8, if k = 2 .
Proof. Clearly, for k = 0 and k > 3 we always have F (x + e i ) = F (x) so in these cases it follows that ᾱF,i = 0. The cases k = 1 and k = 3 are symmetric, and, using k = 1, we have Āi-1 = (0, 0, 0, x i+1 , x i+2 ) , Āi = (x i-2 , 0, 0, 0, x i+2 ) , and Āi+1 = (x i-1 , x i-1 , 0, 0, 0) .

By the inclusion-exclusion principle, it follows that

Āi-1 ∪ Āi ∪ Āi+1 = Āi-1 + Āi + Āi+1 -Āi-1 ∩ Āi -Āi-1 ∩ Āi+1 -Āi ∩ Āi+1 + Āi-1 ∩ Āi ∩ Āi+1 = 3 × 4 -2 -1 -2 + 1 = 8 .
This yields ᾱF,i = 8/2 4 = 1/2. The proof for the case k = 2 is similar to that of k = 1 so we leave this to the reader.

Remark 5. If we instead use the nor-function, then ᾱF,i = 1/2 when n 5. Remark 6. In [START_REF] Shmulevich | Activities and sensitivities in Boolean network models[END_REF], activity is defined with respect to f instead of F and its i th argument. With this context, ᾱf,i (x) = E I[f (x + e i ) = f (x)] . Clearly, we always have ᾱf,i ᾱF,i . As an example, for circle graph of girth 5 and threshold-1 functions it can be verified that ᾱf,i = 0.25 and we have already shown that ᾱF,i = 0.5 in this case.

Activity over d-Regular Trees

The case of d-regular trees is natural as a starting point. Here the sets A j (or more precisely, the sets n[j]) with j = i only overlap at vertex i. As a result, when we condition on x i = m, the resulting sets are independent. More generally, this will hold if the girth of the graph is at least 5.

The Boolean bi-threshold function τ i,k01,k10,n : K n -→ K generalizes standard threshold functions and is defined by [START_REF] Kauffman | The origins of order: Self-organization and selection in evolution[END_REF] where the integers k 01 and k 10 are the up-and down-thresholds, respectively. Here i is a designated vertex -it will be the index of a vertex function. If the up-and down-thresholds are the same we get standard threshold systems. Proposition 7. Let X be a d-regular graph of girth 5, and F the GDS map over X with the bi-threshold vertex functions as in Equation [START_REF] Kauffman | The origins of order: Self-organization and selection in evolution[END_REF]. Then the activity of F with respect to vertex i is given by

τ i,k01,k10,n (x 1 , . . . , x n ) =      1, if x i = 0 and n j=1 x j k 01 0, if x i = 1 and n j=1 x j < k 10 x i , otherwise,
ᾱF,i =1 - 2 d -d-1 k01-1 -d-1 k10-2 2 d d + 1 2 k=k01,k10 d k-1 2 d 2 d-1 -d-1 k10-2 2 d-1 k-1 2 d-1 -d-1 k01-1 2 d-1 d-(k-1) . ( 11
)
Proof. Let B denote the union of A j 's for all j = i as in [START_REF] Goles | Neural and Automata Networks: Dynamical Behaviour and Applications[END_REF] and note that B c is the event that none of the A j 's occur for j = i. Using girth 5 and the resulting independence from conditioning on x i we can write

Pr(B c ) = 1 2 Pr(B c | x i = 0) + 1 2 Pr(B c | x i = 1) = 1 2 j∈n[i] j =i A c j | x i = 0 + 1 2 j∈n[i] j =i A c j | x i = 1 = j∈n[i] j =i A c j | x i = 0 = j∈n[i] j =i Pr A c j | x i = 0 . (12) Next we have Pr A c j | x i = 0 = 1 2 Pr A c j | x i = 0 and x j = 0 + 1 2 Pr A c j | x i = 0 and x j = 1 = 1 2 • 2 d-1 -d-1 k01-1 2 d-1 + 1 2 • 2 d-1 -d-1 k10-2 2 d-1 = [2 d - d -1 k 01 -1 - d -1 k 10 -2 ]/2 d , which substituted into Equation (12) yields Pr(B c ) = 2 d -d-1 k01-1 -d-1 k10-2 2 d d . (13)
Next, we compute the probability of A i ∩ B c as

Pr(A i ∩ B c ) = 1 2 Pr(A i ∩ B c | x i = 0) + 1 2 Pr(A i ∩ B c | x i = 1) = 1 2 Pr(A i | x i = 0) • Pr(B c | A i and x i = 0) + 1 2 Pr(A i | x i = 1) • Pr(B c | A i and x i = 1) = d k01-1 2 d+1 2 d-1 -d-1 k10-2 2 d-1 k01-1 2 d-1 -d-1 k01-1 2 d-1 d-(k01-1) + d k10-1 2 d+1 2 d-1 -d-1 k10-2 2 d-1 k10-1 2 d-1 -d-1 k01-1 2 d-1 d-(k10-1) = 1 2 k=k01,k10 d k-1 2 d 2 d-1 -d-1 k10-2 2 d-1 k-1 2 d-1 -d-1 k01-1 2 d-1 d-(k-1)
. (14) Substituting Equation ( 13) and ( 14) into Equation (8) leads to Equation [START_REF] Kuhlman | Attractor stability in nonuniform boolean networks[END_REF], which ends the proof.

Since the standard threshold function is a special case of the bi-threshold function when k 01 and k 10 coincide, it is straightforward to obtain following corollary. Corollary 8. If F is the GDS map with k-threshold vertex functions over a d-regular graph of girth 5, then the activity of F with respect to vertex i is

ᾱF,i = 1 - 2 d -d k-1 2 d d + d k-1 2 d 2 d-1 -d-1 k-2 2 d-1 k-1 2 d-1 -d-1 k-1 2 d-1 d-(k-1) . ( 15
)
We next consider the nor-function.

Proposition 9. Let X be a d-regular graph of girth 5 and F the GDS map over X induced by the nor-function. Then the activity of F with respect to i is given by

ᾱF,i = 1 -1 - 1 2 d d + 1 2 - 1 2 d d . (16)
Proof. Conditioning on x i = 0 and using independence we have

Pr (B c ) = Pr   j∈n(i) A c j   = j∈n(i) Pr (A j ) . (17)
For a state x with x i = 0 to be in Āj all remaining d states of Āj must be zero leading to Pr Āc

j = 1 -1 2 d and Pr Bc = 1 - 1 2 d d . (18)
In order to calculate Pr (A i ∩ B c ) we note that Pr (A i ∩ B c ) = Pr (A i ) Pr (B c |A i ) and again use independence to obtain

Pr Bc | Āi = j∈n(i) Pr Āc j | Āi . (19)
Note that Pr Āj | Āi = 1/2 d-1 so that Pr Āc j | Āi = 1-Pr Āj | Āi = 1-1/2 d-1 which substituted into [START_REF] Shmulevich | Activities and sensitivities in Boolean network models[END_REF] gives

Pr Bc | Āi = 1 - 1 2 d-1 d .
Noting that Pr( Āi ) = 1/2 d we obtain the third term in [START_REF] Pomerance | The effect of network topology on the stability of discrete state models of genetic control[END_REF], finishing the proof.

Square Lattices

In this section we consider graphs with type-4 edges or girth 4. Here the 1neighborhoods n[j] (with j = i) may intersect, the key aspect we want to address here. As an example, the reader may verify that for threshold-2 functions and Circle 4 , the activity of any vertex is 3/4 and not 7/8 as when n 5 in Proposition 4.

As a specific case, take as graph X a regular, square 2-dimensional lattice. It may be either infinite or with periodic boundary conditions. In the latter case, we assume for simplicity that its two dimensions are at least 5. This graph differs from the 4-regular tree by introduction of type-4 edges: sets A j and A j+1 of A i , when conditioned on the state of vertex i, are no longer independent. The graph has cycles of size 4 containing i. We illustrate this case using nor-functions as these allow for a somewhat simplified evaluation. We discuss more general cases and girth-3 graphs in the Summary section.

β 1 β 2 β 3 β 4 i S1 S2 S3 S4 j 1 j 2 j 3 j 4 j 4 i i i i j 1 j 2 j 3 β 1 β 1 β 2 β 2 β 3 β 3 β 4 β 4
Fig. 3. The subgraph of a torus that includes X(i; 2) at center. The subgraphs S l , each containing the vertices associated to an A l , l ∈ {1, 2, 3, 4}, are also shown separated from the center torus, with "center" vertex j . The overlapping or common vertices, β , are also denoted. We have vectors β = (β1, β2, β3, β4) and xj = (xj 1 , xj 2 , xj 3 , xj 4 ), where xj is the state of the "center" vertex j of A , and where β is a common vertex in A and A +1 ( is always modulo 4).

Proposition 10. Let X be the 2-dimensional lattice as above where every vertex has degree 4, and let F be the GDS map over X induced by nor-functions. Then the activity of F for any vertex i is ᾱF,i = 1040/2 12 .

Proof. The neighborhoods of i involved are illustrated in Figure 3. We rewrite (8) as follows

Pr   j∈n[i] A j   = Pr (B) + Pr (A i ) (1 -Pr (B|A i )) . (20)
To determine |B|, refer to Figure 3. With indices p, q, r, s ∈ {1, 2, 3, 4} we have

|A 1 ∪ A 2 ∪ A 3 ∪ A 4 | = 4 p=1 A p - p<q |A p ∩ A q | + p<q<r |A p ∩ A q ∩ A r | - p<q<r<s |A p ∩ A q ∩ A r ∩ A s | , (21)
which, along with Equation [START_REF] Shmulevich | The role of certain post classes in boolean network models of genetic networks[END_REF], is also valid if we condition on x i = 0 in every set. We take i = j with ∈ {1, 2, 3, 4} and let j denote the vertex at the center of n[j ] and i the vertex at the center of n[i]. Here |X(i; 2)| = 13. Using the symmetry of the sets Āj and the fact that a state x is in the set Āj precisely when x[j ] = 0 leads to

4 =1 | Āj | = 4 • 2 8 .
For the second term on the right in [START_REF] Xiao | The impact of function perturbations in boolean networks[END_REF] we have two cases for intersections: (i) two adjacent vertices j , j +1 ∈ n [i] with all indices modulo 4, of which there are four instances, and (ii) two non-adjacent vertices j , j +2 ∈ n [i], of which there are two instances. In the first case we obtain | Āj ∩ Āj +1 | = 2 5 , while in the second case we have | Āj ∩ Āj +2 | = 2 4 , making the second term on the right in ( 21)

p<q | Ājp ∩ Ājq | = 4 • 2 5 + 2 • 2 4 . (22)
The third sum appearing on the right in [START_REF] Xiao | The impact of function perturbations in boolean networks[END_REF] contains four terms all corresponding to an intersection of three sets A j , and we obtain

p<q<r | Ājp ∩ Ājq ∩ Ājr | = 4 • 2 2 . ( 23
)
Finally, the intersection of all four sets Āj has size 1, and we get

Pr( B) = | B|/2 12 = 4 • 2 8 -(4 • 2 5 + 2 • 2 4 ) + 4 • 2 2 -1 /2 12 . (24)
We next determine Pr (B|A i ). For a state x to be in A i we must have x which, together with (24) in [START_REF] Shmulevich | The role of certain post classes in boolean network models of genetic networks[END_REF] gives the stated result of ᾱF,i = 1040/2 12 .

[i] = 0 so that |A i | = 2

Summary and Research Directions

We have introduced an extension of the notion of activity proposed by Shmulevich and Kauffman [START_REF] Shmulevich | Activities and sensitivities in Boolean network models[END_REF]. This extension takes into account the impact of the network structure when studying E I[F (x) = F (x + e i )] , which estimates how likely the perturbation e i will cause successor states to diverge. Naturally, orbits that initially separate may later converge. Nonetheless, this notion of activity provides a measure for sensitivity with respect to initial conditions. Possibly interesting avenues for further work includes studying asynchronous systems. If the vertex functions are applied sequentially according to for example a permutation update sequence, are there effective ways of relating activity and the permutation? If so, are there principles connecting network structure and update sequence that allows one to minimize or maximize the activity of one or more vertices? Square grids have type-4 edges and cycles of length 4 involving the vertex i. If we permit more general graphs with type-3 edges we naturally obtain cycles of length 3 containing i. The notion of cluster coefficient quantifies the number of triangles incident to i. Is it possible to relate activity and cluster coefficient? Of course, cluster coefficient is solely a graph property and includes nothing about vertex functions. Can one still find such a relation for a specific choice of vertex functions?

Finally, we considered arbitrary initial states x ∈ K n . What can be said about activity if we restrict x to be a periodic point? We invite the reader to explore this -some initial results on attractor activity are given in [START_REF] Kuhlman | Attractor stability in nonuniform boolean networks[END_REF].

Fig. 2 .

 2 Fig. 2. Activity of ECA by rule number. With the exception of the constant rules of activity 0, all rules have activity 1/2 with most rules exceeding 3/4.

4 =12 4 1 - 1 2 8 2 7 - 2 5

 4172 |A j | = 4 • 2 5 , p<q |A jp ∩ A jq | = 4 • 2 3 + 2 • 2 2 , p<q<r |A jp ∩ A jq ∩ A jr | = 4 • 2 , |A j1 ∩ A j2 ∩ A j3 ∩ A j4 | = 1 ,(25) leading to the expression Pr Āi ∩ Bc = Pr Āi 1 -Pr B| Āi = 1 -2 3 + 2 3 -1 ,

  8 . Conditioning on this, we can calculate |

	4 =1 A j | as above.
	The reader can verify that

Corresponding author: Henning S. Mortveit; email: henning.mortveit@vt.edu; Telephone:

+1 540 231-5327; Fax: +1 540 231 2891

Acknowledgments

We thank our external collaborators and members of the Network Dynamics and Simulation Science Laboratory (NDSSL) for their suggestions and comments. This work has been partially supported by DTRA Grant HDTRA1-11-1-0016.