Project topics and materials
Get Complete Project Material File(s) Now! »
Automata network representations
In this section, the notion of standard representation is introduced. A standard representation of a certain family F of automata networks is a family F⇤ of Boolean circuits which computes, via some coding function depending on the alphabet of the family, each automata network in the usual way. Note that each circuit can be encoded in multiple ways as well it is possible that the circuit is considered to be given in its standard encoding. In addition, a representation could be virtually any kind of object which encodes in some way a circuit family simulating the original automata network family. Then, in general, a standard representation is considered to be a particular language in which any word encodes in an efficient way the encoding of some circuit computing an automata network in the family. In order to motivate an analysis on how could be a natural representation in the context of concrete examples of automata network families, we present here different representations and we show that they are related to the circuit representation.
Representation of some particular families
Observe that the communication graph is an interesting piece of information in the context of describing an automata network, as it contains, the structure of the global rule, expressed as the adjacency of nodes in latter network. However, as we will see in this section, constructing the communication graph of a given automata network (provided that this automata network is represented for example as a circuit) is not always an easy task. Conversely, if some repre-sentation including the information of the automata network (plus for example, information about local rules) is provided, it could be also hard to construct a circuit representation for the global rule of the automata network. We will illustrate this fact by analyzing three exam-ples of canonical types of families: bounded degree networks, CSAN and algebraic families. The first one is characterized by a communication graph which has bounded degree, i.e. there exists a constant Δ 2 N (not depending on the size of the network) such that maximum de-gree is at most Δ. The second one was widely presented in previous sections and it roughly corresponds to the family of all set-valued functions described by labelled communication graphs. Finally, an algebraic family is essentially a family of linear maps in the case in which Q is seen as a finite field and Qn as a linear space. We show in the latter examples that there exists a natural representation that is based on the properties of the family. For instance, it is possible to deduce that for the bounded degree families, the bounded degree parameter provides a way to store information in an efficient way. This is because local functions do not depend in the size of the network. In addition, we have also an efficient representation for the case of CSAN since local functions are set-valued (locally every node depends only on the set of states given by the states of their neighbors) and thus they do not depend on the size of the network. Finally, we have the case of linear maps that can be represented as matrices.
Note that, when we think at the latter collection of automata networks as a CSAN family, we can directly work with a structure that can be represented efficiently. This is because, a CSAN family is a collection of labeled graphs and thus, the construction of the simulator can be done by simply reading the adjacency information of the graph and replacing each node by some specific gadget. More precisely, we have that a CSAN is a graph G together with some circuit family which represents local functions (i.e. and ⇢). Each local function will depend only on the local configuration composed by a node and its neighbors. In addition, for a fixed CSAN family, a collection of set-valued functions and edge-labels is provided independently of the structure of each graph as they depend on the possible sets of elements in the alphabet Q (note that what makes different two networks in one family is the position of labels but local functions are chosen from the same fixed set). Thus, we can represent a CSAN family F by a collection of labeled graphs G and a circuit family ⇤. We call this representation a succinct representation for CSAN F. Since circuit family ⇤ depends only in the size of the alphabet and since we are considering that the alphabet is fixed, we will usually omit ⇤ and just write G as a succinct representation for F and we will denote a CSAN (G,,⇢ ) 2 F by simply G (where of course G is a labeled graph in G). Note that since the alphabet size is constant, a succinct representation is, in particular, a standard representation for CSAN family as an automata network family. Formally, the language LG containing the encoding of each labeled graph in G together with the standard encoding of constant circuit family ⇤ is a standard representation for CSAN family F.
A briefly note in the definition of a bounded degree family is recalled: let k 2 N, F be an automata network family and G be a collection of graphs such that for each F 2 F, F has an interaction graph GF 2 G. We say F is a bounded degree family of degree k 2 N if for each F , GF satisfies Δ(GF ) k. Thus, a representation for F is simply an encoding of G as an adjacency list and a list of circuits (G, {fi : i 2 V (GF )} representing local functions. Note that each of these circuits has constant depth as the number of variables is at most k. Let wF 2 {0, 1}⇤ an encoding of (G, {fi : i 2 V (GF )} then, we define &(G) : {wF : F 2 F} and we call it a graph representation. Let us fix some positive constant Δ . It is natural to consider the family of automata networks whose interaction graph has a maximum degree bounded by Δ (see Remark 3.5 in page 43). We associate to this family the following representation: an automata network F is given as pair (G, (⌧v)v2V (G )) where G is a communication graph of F of maximum degree at most Δ and (⌧v)v2V (G) is the list for all nodes of G of its local transition map Fv of the form Qd ! Q for d Δ and represented as a plain transition table of size |Q|d log(|Q|).
Remark 2.1 Given any CSAN family, there is a DLOGSPACE algorithm that transforms a bounded degree representation of an automata network of the family into a CSAN repre-sentation: since all local maps are bounded objects, it is just a matter of making a bounded computation for each node.
Computing interaction graphs from representations.
One of the key differences between all the representations presented so far is in the infor-mation they give about the interaction graph of an automata network. For instance, it is straightforward to deduce the interaction graph of a linear network from its matrix repre-sentation in DLOGSPACE. At the other extreme, one can see that it is NP-hard to decide whether a given edge belongs to the interaction graph of an automata network given by a circuit representation: indeed, one can build in DLOGSPACE from any SAT formula with n variables a circuit representation of an automata network F : {0, 1}n+1 ! {0, 1}n+1 with F (x)1 = ( xn+1 if (x1, . . . , xn) is true, 0 else.
This F is such that node 1 depends on node n + 1 if and only if is satisfiable. For automata networks with communication graphs of degree at most Δ, there is a poly-nomial time algorithm to compute the interaction graph from a circuit representation: for each node v, try all the possible subsets S of nodes of size at most Δ and find the largest one such that the following map x 2 QS 7!Fv( (x)) effectively depends on each node of S, where (x) w is xw if w 2 S and some arbitrary fixed state q 2 Q else. Note also, that we can compute a bounded degree representation in poly-nomial time with the same idea.
In the CSAN case, the situation is ambivalent. On the one hand, the interaction graph can be computed in polynomial time from a CSAN representation because for any given node v the following holds: either v is a constant map and then v has no dependence, or v is not constant and then the neighborhood of v in the CSAN representation is exactly the neighborhood of v in the interaction graph. On the other hand, a polynomial time algorithm to compute the interaction graph from a circuit representation would give a polynomial algo-rithm solving Unambiguous- SAT (which is very unlikely, following Valiant-Vazirani theorem [3, Theorem 9.15]). Indeed, any “dirac” map : {0, 1}n ! {0, 1 } with (x) = 1 if and only if x1 · · · xn = b1 · · · bn can be seen as the local map of a CSAN network because it can be written as ({⇢i(xi) : 1 i n}) where ⇢i((xi) = xi if bi = 1 and ¬xi else, and is the map S ✓ Q 7! 1 if S = {1} 0 else.
A constant map can also be seen as the local map of some CSAN network. Therefore, given a Boolean formula with the promise that is at has at most one satisfying assignment, one can easily compute the circuit representation of some CSAN network which has some edge in its interaction graph if and only if is satisfiable.
Standard representation
Recall that given a fixed alphabet Q, a family of automata networks is a collection of functions F = (Fs)s2N satisfying that for each s 2 N there exist some n(s) 2 N such that Fs : Qn(s) ! Qn(s) is an automata network. We fix for any alphabet Q an injective map mQ : Q ! {0, 1}kQ which we extend cell-wise for each n to mQ : Qn ! {0, 1}kQn. Given an automata network F : Qn ! Qn, a circuit encoding of F is a Boolean circuit C : {0, 1}kQn ! {0 , 1}kQn such that mQ F = C mQ on Qn . We also fix a canonical way to represent circuits as words of {0, 1}⇤ (for instance given by a number of vertices, the list of gate types positioned at each vertex and the adjacency matrix of the graph of the circuit).
Let F be a family of automata networks over alphabet Q. A standard representation F⇤ for F is a language LF ✓ {0, 1}⇤ together with a DLOGSPACE algorithm such that:
• the algorithm transforms any w 2 LF into the canonical representation of a circuit encoding C(w) that codes an automata network Fw 2 F;
• for any F 2 F there is w 2 LF with F = Fw.
The default general representations we will use are circuit representations, i.e. repre-sentations where w 2 LF is just a canonical representation of a circuit. In this case the DLOGSPACE algorithm is trivial (the identity map). However, we sometimes want to work with more concrete and natural representations for some families of networks: in such a case, the above definition allows any kind of coding as soon as it is easy to deduce the canonical circuit representation from it.
From now on, a family of automata networks will be given as a pair (F, F⇤ ) where F is the set of automata networks and F⇤ a standard representation. In order to give some intuition regarding this latter general definition, examples of standard representations for specific families of automata networks are given in the next section. Particularly, bounded degree case and CSAN case are explored. In addition, we discuss how and when one can easily construct the circuit representation of an automata network from one of the latter representations.
Table of contents :
Introduction
1 Preliminaries
1.1 Automata networks
1.1.1 Elements of Graph Theory
1.1.2 Automata networks as discrete dynamical systems
1.1.3 Some important automata network families
1.1.4 Bounded degree automata networks
1.1.5 Algebraic automata networks
1.1.6 Freezing automata networks
1.1.7 Non-deterministic automata networks
1.2 Elements of computational complexity
1.2.1 Counting complexity
1.2.2 Parametric complexity
1.2.3 Parellel computing and NC
1.3 Toolbox
1.3.1 Automata networks dynamics
1.3.2 Treewidth and tree decompositions
1.3.3 Fast parallel subroutines
1.3.4 Arithmetic results
2 Measuring dynamic albehavior
2.1 Automata network representations
2.1.1 Representation of some particular families
2.1.2 Computing interaction graphs from representations.
2.1.3 Standard representation
2.2 Simulation and universality
2.2.1 Simulation between automata networks
2.2.2 Simulation between families of automata networks
2.3 Decision problems and automata network dynamics
2.4 Universal automata network families
3 Gadget complexity: from local to global behavior
3.1 Putting pieces together: glueing automata networks
3.2 Computing on automata networks
3.2.1 G-networks
3.2.2 G-gadgets and simulation of G-networks
3.2.3 Gadget glueing
3.3 Some useful families of G-networks: Gm-networks and Gm,2-networks
3.3.1 Closure and synchronous closure
3.3.2 Super-polynomial periods without universality
3.3.3 Conjunctive networks and Gconj-networks
3.3.4 Super-polynomial transients without universality
4 Describing asynchronous dynamics: adeterministic approach
4.1 Update schemes
4.1.1 Periodic update schemes
4.1.2 Projection systems
5 Concrete symmetric automatanetworks: a case study
5.1 Symmetric conjunctive networks
5.1.1 Local clocks update scheme
5.1.2 Periodic update schemes
5.1.3 Firing memory schemes
5.2 Locally positive symmetric signed conjunctive networks
5.2.1 Block sequential update schemes
5.2.2 Local clocks update schemes
5.3 Symmetric signed conjunctive networks
5.3.1 Block sequential update schemes
5.4 Symmetric min-max networks
5.4.1 Block sequential update schemes
6 Freezing dynamics
6.1 Specification checking problem: a canonical model checking problem to capture many classical dynamical problems.
6.1.1 Localized Trace Properties
6.1.2 A fast parallel algorithm for Specification Checking
6.1.3 W[2]-hardness results
6.1.4 Hardness results for polynomial treewidth networks
6.2 Counting complexity on freezing automata networks: a case study.
6.2.1 Contagion-Probability is #P-Complete
6.2.2 Polynomial time algorithm for maximum degree 4
Discussion
Bibliography
