# Modeling Delayed Dynamics in Biological Regulatory Networks from Time Series Data +
## 2 Automata Networks  
We present in this section the definition and the semantics of automata networks. The enrichment of the automata networks with delays and the corresponding new semantics are presented in Section 3. Definition 1 introduces the Automata Network (AN) [27; 28; 29] as a model of finite-state machines having transitions between their _local state_ conditioned by the state of other automata in the network. A _local state_ of an automaton is noted by \(a_{i}\), where \(a\) is the automaton identifier, and \(i\) is the expression level within \(a\). At any time, each automaton has exactly one _active local state_, and the set of _active local states_ is called the _global state_ of the network. The concurrent interactions between automata are defined by a set of local transitions. Each local transition has this form \(\tau=a_{i}\overset{\ell}{\rightarrow}a_{j}\), with \(a_{i}\), \(a_{j}\) being local states of an automaton \(a\) called, respectively, the origin and destination of \(\tau\), and \(\ell\) is a (possibly empty) set of local states of automata other than \(a\) (with at most one local state per automaton). Notation: Given a finite state \(A\), \(\wp(A)\) is the power set of \(A\). Given a network \(N\), \(\mathit{state}(N,t)\) is the state of \(N\) at a time step \(t\in\mathds{N}\). **Definition 1** (Automata Network (AN)). : _An automata network is a triple \((\Sigma,\mathcal{S},\mathcal{T})\) where:_  
* \(\Sigma=\{a,b,\dots\}\) _is the finite set of automata identifiers;_
* _For each_ \(a\in\Sigma\)_,_ \(\mathcal{S}(a)=\{a_{i},\dots,a_{j}\}\)_, is the finite set of local states of automaton_ \(a\)_;_ \(\mathcal{S}=\prod_{a\in\Sigma}\mathcal{S}(a)\) _is the finite set of global states and_ \(\mathbf{LS}=\cup_{a\in\Sigma}\mathcal{S}(a)\) _denotes the set of all of the local states._
* \(\mathcal{T}=\{a\mapsto\mathcal{T}_{a}\mid a\in\Sigma\}\)_, where_ \(\forall a\in\Sigma,\mathcal{T}_{a}\subset\mathcal{S}(a)\times\wp(\mathbf{LS} \setminus\mathcal{S}(a))\times\mathcal{S}(a)\) _with_ \((a_{i},\ell,a_{j})\in\mathcal{T}_{a}\Rightarrow a_{i}\
eq a_{j}\)_, is the mapping from automata to their finite set of local transitions._  
**Example 1**. : _Figure 1 represents an automata network, \(\mathcal{AN}=(\Sigma,\mathcal{S},\mathcal{T})\), with four automata (\(\Sigma=\{a,b,c,d\}\)), such that \(\mathcal{S}(a)=\{a_{0},a_{1}\}\), \(\mathcal{S}(b)=\{b_{0},b_{1}\}\), \(\mathcal{S}(c)=\{c_{0},c_{1},c_{2}\}\) and \(\mathcal{S}(d)=\{d_{0},d_{1},d_{2}\}\), and five local transitions,_  
A global state of a given AN consists of a set of all active local states of each automaton in the network. The active local state of a given automaton \(a\in\Sigma\) in a state \(\zeta\in\mathcal{S}\) is denoted \(\zeta[a]\). For any given local state \(a_{i}\), we also note \(a_{i}\in\zeta\) if and only if \(\zeta[a]=a_{i}\). For each automaton, it cannot have more than one active local state at one global state. **Definition 2** (Playable local transition). : _Let \(\mathcal{AN}=(\Sigma,\mathcal{S},\mathcal{T})\) be an automata network and \(\zeta\in\mathcal{S}\), with \(\zeta=\mathit{state}(\mathcal{AN},t)\). We denote \(P_{t}\) the set of playable local transitions in \(\mathcal{AN}\) at time step \(t\) by: \(P_{t}=\{a_{i}\overset{\ell}{\rightarrow}a_{j}\in\mathcal{T}\mid\ell\subseteq \zeta\wedge a_{i}\in\zeta\text{ with state}(\mathcal{AN},t)=\zeta\}\)._  
The dynamics of the AN is performed thanks to the global transitions. Indeed, the transition from one state \(\zeta_{1}\) to its successor \(\zeta_{2}\) is satisfied by a set of the playable local transitions (Definition 2) at \(\zeta_{1}\). **Definition 3** (Global transitions). : _Let \(\mathcal{AN}=(\Sigma,\mathcal{S},\mathcal{T})\) be an automata network and \(\zeta_{1},\zeta_{2}\in\mathcal{S}\), with \(\zeta_{1}=\mathit{state}(\mathcal{AN},t)\) and \(\zeta_{2}=\mathit{state}(\mathcal{AN},t+1)\). Let \(P_{t}\) be the set of playable local transitions at \(t\).