key: cord-0046153-7c0ltv2c
authors: Bridoux, Florian; Gadouleau, Maximilien; Theyssier, Guillaume
title: On Simulation in Automata Networks
date: 2020-06-24
journal: Beyond the Horizon of Computability
DOI: 10.1007/978-3-030-51466-2_24
sha: 1ca353a5286149fda83a9b610ade21746a00dc2a
doc_id: 46153
cord_uid: 7c0ltv2c

An automata network is a finite graph where each node holds a state from some finite alphabet and is equipped with an update function that changes its state according to the configuration of neighboring states. More concisely, it is given by a finite map [Formula: see text]. In this paper we study how some (sets of) automata networks can be simulated by some other (set of) automata networks with prescribed update mode or interaction graph. Our contributions are the following. For non-Boolean alphabets and for any network size, there are intrinsically non-sequential transformations (i.e. that can not be obtained as composition of sequential updates of some network). Moreover there is no universal automaton network that can produce all non-bijective functions via compositions of asynchronous updates. On the other hand, we show that there are universal automata networks for sequential updates if one is allowed to use a larger alphabet and then use either projection onto or restriction to the original alphabet. We also characterize the set of functions that are generated by non-bijective sequential updates. Following Tchuente, we characterize the interaction graphs D whose semigroup of transformations is the full semigroup of transformations on [Formula: see text], and we show that they are the same if we force either sequential updates only, or all asynchronous updates.

An automata network is a network of entities each equipped with a local update function that changes its state according to the states of neighboring entities. Automata networks have been used to model different kind of networks: gene networks, neural networks, social networks, or network coding (see [9] and references therein). They can also be considered as a model of distributed computation with various specialized definitions [18, 19] . The architecture of an automata network can be represented via its interaction graph, which indicates which update functions depend on which variables. An important stream of research is to determine how the interaction graph affects different properties of the network or to design networks with a prescribed interaction graph and with a specific dynamical property (see [8] for a review of known results). On the other hand, automata networks are usually associated with an update mode describing how local update functions of each entity are applied at each step of the evolution. In particular, three categories of update modes can be distinguished: sequential (one node update at a time), asynchronous (any subset of nodes at a time) or synchronous (all nodes simultaneously). Studying how changing the update mode affects the properties of an automata network with fixed local update functions is another major trend in this field [12, 13, 15] . Comparing the computational power of sequential and parallel machines is of course at the heart of computer science, but the questioning on update modes is also meaningful for applications of automata networks in modeling of natural systems where the synchronous update mode is often considered unrealistic.

For both parameters (interaction graphs and update modes), the set of properties that could be potentially affected is unlimited. In this paper, instead of choosing a set of properties to analyze, we adopt an intrinsic approach: we study how some (sets of) automata networks can be simulated by some other (set of) automata networks with prescribed update mode or interaction graph.

Notations. We will always consider alphabets of the form [[q]] = {0, . . . , q − 1} for some q and usually denote by n the number of nodes of the network which are identified by integers in the interval [1, n] . An automata network is a map f :

The rank of f is the size of its image. For any set of coordinates V ⊆ [1, n] ,

] n denotes the following map:

The notation is extended to words of subsets w = (w 1 , . . . , w k ) as follows:

For v ∈ [1, n] we overload this notation by f (v) = f ({v}) . We will often consider semigroups of functions under compositions: X where X is a set of functions that denotes the semigroup generated by compositions of elements of X. We denote the fact that S 1 is a sub-semigroup of S 2 by S 1 ≤ S 2 . For any set X, Sym(X) is the set of permutations on X. We denote the set of all networks f :

] n as F(n, q). We denote by Sym(n, q) the set of f ∈ F(n, q) which are bijective and by Sing(n, q) the set of f ∈ F(n, q) which are non-bijective. For any set F of functions in F(n, q), what they can simulate (asynchronously, sequentially, synchronously) is denoted as follows:

Our Contributions. In this paper, we are further developing both strands of the theory of simulation of automata networks. We make the following contributions. We first consider simulation by a single network. Firstly, we show that for any q ≥ 3 and any n ≥ 2, there exists a network g ∈ F(n, q) which is not sequentially simulatable. Secondly, we consider asynchronous simulation, and we show that there is no asynchronously complete network: for all f ∈ F(n, q), Sing(n, q) ≤ f Asy . This is a clear strengthening of the result in [2] for sequential simulation. Thirdly, we extend the framework to let a network over a large alphabet f ∈ F(n, q ) simulate a network g ∈ F(n, q) over a smaller alphabet. We consider two ways to extend the alphabet, and for each we prove the existence of sequentially complete networks for q = 2q and q = q + 1, respectively. We then consider simulation by large sets of networks. The seminal result in [4] shows that instructions (updates of the form f (v) for some v ∈ [1, n]) can simulate any network; in this paper, we determine what singular instructions can simulate (and even idempotent instructions for q ≥ 3). We finally strengthen the main result in [16] by showing that it also holds when considering sequential and asynchronous updates as well.

Proof. Complete proofs of all lemmas, propositions and theorems can be found in [3] .

We say g ∈ F(n, q) is sequentially simulatable if g ∈ f Seq for some f ∈ F(n, q). Recall that unless n = q = 2 any g ∈ Sym(n, q) is sequentially simulatable since there is a universal f ∈ F(n, q) such that f Seq = Sym(n, q) [7] . Concerning non-bijective maps, the situation is radically different for non-Boolean alphabets as shown in the following theorem. For any function φ ∈ F(n, q), we denote by O(()φ) the set of its orphans:

The analysis of oprhans configurations under sequential updates is the key behind the following theorem. 

F. Bridoux did an exhaustive search in F(n, 2) with n = 2 and n = 3 to test which one are sequentially simulatable [1] . It turns out that all f ∈ F(3, 2) are sequentially simulatable. However, some functions in F(2, 2) are not and one example is the circular permutation 00 → 01 → 11 → 10 → 00 [1, Proposition 12] . More details (including the code of the test program) are available at http:// theyssier.org/san2020.

In this section, we consider asynchronous simulation, where at each step we allow any update f (T ) for T ⊆ [1, n] . We then refine the result in [2] that there is no network that can sequentially simulate all singular networks.

We say that a function h :

Proof. Suppose, for the sake of contradiction, that Sing(n, q) ≤ f Asy . We first show that not all coordinate functions of f are balanced. There exists S ⊆ [1, n] such that f (S) has rank q n −1. (Otherwise, no function in f Asy has rank q n −1.)

Let g ∈ Sing(n, q) not be deficient, and have a nontrivial g v ; and suppose g =

Similarly to Theorem 1, the obstacle in Theorem 2 was found in the set of maps of rank q n − 1. We now show that maps of rank q n − 2 form another obstruction to having complete simulation in the asynchronous case. Let T (n, q) be the set of networks in F(n, q) whose rank is not equal to q n − 1. It is clear that T (n, q) is a semigroup, generated by maps of rank q n or q n − 2.

Proof. Suppose, for the sake of contradiction, that T (n, q) ≤ f Asy . Firstly, all the coordinate functions of f are balanced. Indeed, let g(x) = x + (1, . . . , 1) and By an argument similar to the proof of Theorem 2, there is no S ⊆ [1, n] such that f (S) is of type I. Let g be of type I and let us express it as g = f (w1···w k ) . Each f (w l ) has rank at least q n − 2, and there exists 1 ≤ i ≤ k such that f (wi) is singular. By the argument above, f (wi) is of type II and so is h

, then g has rank at most q n − 3; otherwise |g −1 (h (a))| = |g −1 (h (b))| = 2 and hence g is of type II, which is the desired contradiction.

As said earlier, there is no universal automata network in F(n, q) able to sequentially simulate all functions of F(n, q) (actually Theorem 2 gives a stronger negative result). In this section, we revisit this problem when the simulator is allowed to use a larger alphabet. In this case we can consider two natural types of simulations: one requires the simulation to work on any initial configuration of the simulator and uses a projection onto configurations of the simulated functions; the other does not use projection, but works only on initial configurations using the alphabet of the simulated function. Definition 1. Let n ∈ N, 2 ≤ q < q and consider f ∈ F(n, q ). We say that f is (n,q)-universal by factor if there is a surjection π :

where π(x 1 , . . . , x n ) = (π(x 1 ), . . . , π(x n )). f is said (n,q)-universal by initialization if for any h ∈ F(n, q) there is a word w ∈ [1, n] * such that

We are going to show that universality can be achieved for each kind of simulation. In both cases, the larger alphabet allows us to encode more information than the configuration of the simulated function. This additional information is used as a global controlling state that commands transformations applied on the simulated configuration and evolves according to a finite automaton. In the case of simulation by factor, the encoding is straightforward but the global controlling state is uninitialized. The key is to use a control automaton with a synchronizing word (see Fig. 1 ). In the case of simulation by initialization, the difficulty lies in the encoding.

The following theorems were obtained by F. Bridoux during his PhD thesis [1] .

For any q ≥ 2 and n ≥ 3, there exists f ∈ F(n, 2q) which is (n, q)-universal by factor. 

if x = (0) n and (y = 011 or y = 001), 0 if x = 1(0) n−1 and y = 011, x 1 otherwise,

Then we define f by f (x, y) = Ψ (x, y), ρ(y) . We now prove properties about f implying that it is (n, q)-universal by factor. Proof. First, let us remark that updating q times coordinate 3 starting from (x, y), there are two cases: -y = 011 or x 1 = 0 or x 2 = 0 and then the component x is not modified; -y = 011 and x 1 = x 2 = 0, and then the modification x 3 ← x 3 + 1 is applied q times.

Therefore

To show that the update sequence ((3) q , 2, 3, 1, 1, 2, 1, 3) does not modify the component x, it is sufficient to verify the following:

-coordinate 1 is not updated when y ∈ {101, 011, 001}; -coordinate 2 is not updated when y = 111; -when coordinate 3 is updated and y = 011, it is updated q times.

By definition of f ((3) q ,2,3,1,1,2,1,3) , we obtain:

Let us now show that, starting from (x, 101), f can realize three kinds of transformations on x that will turn out to be sufficient to generate all F(n, q).

-Let c ∈ Sym(n, q) be the following circular permutation:

then for any x ∈ [[q]] n we have f (1,2,2,1,(3,4,. ..,n)) (x, 101) = (c(x), 011) because:

-Consider the transposition k = ((0) n ↔ 1(0) n−1 ), then we have, for any

x ∈ [[q]] n , f (2,1,1) (x, 101) = (k(x), 011) because:

-Finally, consider the assignment d = ((0) n → 1(0) n−1 ), then for any x ∈ [[q]] n it holds f (2,1,2,1) (x, 101) = (d(x), 001) because:

Since functions c, k and d generate F(n, q) (see [14] or [11] ), the theorem follows.

For any q ≥ 2 and n ≥ 3q, there is f ∈ F(n, q + 1) which is (n, q)-universal by initialization.

So far we studied what a single function can simulate. We know shift our interest to semigroups generated by some sets of functions.

An instruction is any f (v) for some f ∈ F(n, q) and some v ∈ [1, n] . Burckel showed that any network is the composition of instructions: F(n, q) Seq = f (v) : f ∈ F(n, q), v ∈ [1, n] = F(n, q). As an immediate consequence, any permutation in Sym(n, q) is the composition of permutation instructions: Sym(n, q) is exactly f (v) ∈ Sym(n, q) : f ∈ F(n, q), v ∈ [1, n] . We now determine what singular instructions generate: let Any network f can be seen as a vertex colouring of the Hamming graph H(n, q) (x colored by f (x)). From the proposition above, networks in S(n, q) correspond to improper colouring. Since the chromatic number of H(n, q) is equal to q, we deduce that any network with rank at most q − 1 can be generated by singular instructions. However, the network f (x) = (x 1 + . . . + x n , 0, . . . , 0) cannot be generated by singular instructions, since it generates a proper colouring of the Hamming graph.

A network f is idempotent if f 2 = f . Idempotents are pivotal in the theory of semigroups, for they are the identity elements of the subgroups of a given semigroup. In particular it is interesting to know whether a semigroup S is generated by its set of idempotents, because then any element s ∈ S can be expressed as a product of consecutively distinct idempotents: s = e 1 e 2 . . . e k . We remark that if f ∈ S(n, q) is idempotent and has rank q n − 1, then it must be an assignment instruction. Theorem 5. S(n, q) is generated by assignment instructions for q ≥ 3.

The previous result could be proved using the so-called fifteen-puzzle. In the original puzzle, an image is cut into a four-by-four grid of tiles; one of the tiles is removed, thus creating a hole; the remaining fifteen tiles are scrambled by sliding a tile into the hole. The player is then given the scrambled image, and has to reconstruct it by repeatedly sliding a tile in the hole.

Clearly, this game can be played on any simple graph D, where a hole is created at a vertex (say h), and one can "slide" one vertex into the hole, the hole thus moving to that vertex. If the hole goes back to its original place h, then we have created a permutation of V (D) \ h. The set of all possible permutations is closed under composition and hence it forms a group, called the puzzle group G(D, h). Wilson [17] fully characterised that group for 2-connected simple graphs; we give a simpler version of the theorem below. Proof (Proof of Theorem 7). Clearly, 1 implies 2, which in turn is equivalent to 3. We prove 2 implies 4. Let D such that F(D, q) Asy = F(n, q). By Lemma 1, D is strong. We now prove that D has a vertex of in-degree n. Otherwise, let f ∈ F(D, q) of rank q n − 1. Let a ∈ O(()f ) and b with |f −1 (b)| = 2 (and hence |f −1 (x)| = 1 for any other x). We then have

On the other hand, it is easily seen that for any y ∈

|f −1 v (y)|y mod q = 0.

Doing this componentwise for all v, we obtain x∈ [[q] ] n f (x) = 0, which is the desired contradiction. We prove 4 implies 1. We only need to show that all instructions in F(n, q) belong to F(D, q) Seq . Let u be a vertex of in-degree n, then we already have any instruction updating u. Let v be another vertex, and g be an instruction updating v,

where h is the instruction updating u such that h u = g v •(u ↔ v). Then (u ↔ v) ∈ F(D, q) Seq according to Lemma 1. Thus, any instruction can be generated.

The contrast between the complete sequential simulator for Sym(n, q) and the existence of non-bijective functions that are not sequentially simulatable in the non-Boolean case is striking. We would like first to settle the Boolean case: we conjecture that all functions of F(n, 2) are sequentially simulatable for large enough n. For q ≥ 3, in order to better understand the set of sequentially simulatable networks, one could for instance analyze how much synchronism is required to simulate them (how large are the sets V in the asynchronous updates f (V ) used to simulate them). In particular, one may ask whether, for all n, there exists some network with n entities that require a synchronous update f ( [1,n] ) in order to be simulated asynchronously. Besides, the networks considered in Sects. 2, 3 and 4 have an unconstrained interaction graph. The situation could be very different when restricting all networks to particular a family of interaction graphs (bounded degree, bounded tree-width, etc.). Finally, still concerning interaction graphs, the characterization of Theorem 7 is about reflexive graphs. We would like to extend it to any graph (not necessarily reflexive).

If D is not bipartite and has at least eight vertices, then G(D, h) = Sym(V (D) \ h)

If D is bipartite, then G(D, h) = Alt(V (D) \ h)

Since H(n, q) is not bipartite for q ≥ 3 (and it has at least nine vertices for n ≥ 2), we can apply Wilson's theorem and, after a bit more work

graph) which has vertex set V = [1, n] and has an arc from u to v if and only if f v depends essentially on u, i.e. there exists a, b ∈ [[q]] n such that a V \u = b V \u and f v (a) = f v (b). For any graph D with n nodes, we denote the set of networks in F(n, q) whose interaction graph is a

Note that for any reflexive graph D it holds F(D, q) Seq ⊆ F(D, q) Asy = F(D, q) Syn . The first inclusion is trivial; the equality follows from the fact that for any f ∈ F(D, q) and any S ⊆ [1, n], f (S) belongs to F(D, q) as well. Moreover, it is clear that if F(H, q) Seq = F(n, q), then H is reflexive (otherwise, F(H, q) Seq would not contain any permutation). The reflexive graphs which can simulate the whole of F(n, q) synchronously were classified by

q) Seq contains all permutations of variables of F(n, q)

q) Asy contains all permutations of variables of F(n, q)

Intrinsic simulations and complexities in automata networks. Theses, Aix-Marseile Université

Complete simulation of automata networks

Simulation of automata networks

Closed iterative calculus

Mapping computation with no memory

Computation with no memory, and rearrangeable multicast networks

Computing in permutation groups without memory

On the influence of the interaction graph on a finite dynamical system

Simple dynamics on graphs

Memoryless computation: new results, constructions, and extensions

Classical Finite Transformation Semigroups: An Introduction

Disjunctive networks and update schedules

PSPACE-completeness of majority automata networks

Fundamentals of Semigroup Theory

Synchronism versus asynchronism in monotonic Boolean automata networks

Computation on binary tree-networks

Graph puzzles, homotopy, and the alternating group

Cellular graph automata. I. basic concepts, graph property measurement, closure properties

Cellular graph automata. II. graph and subgraph isomorphism, graph structure recognition

Theorem 7. Let D be a reflexive graph on n vertices. Then the following are equivalent.

A permutation of variables is any network f :=φ defined by f i (x) = x φ(i) for some φ ∈ Sym ([1, n] ). We first show that we can permute variables freely if the graph is strongly connected (and is reflexive for the sequential case). Lemma 1. The following are equivalent for a reflexive graph D.