Théo Plénet

Samira El Yacoubi

Clément Raïevsky

Laurent Lefèvre

Observability and Reconstructibility of Affine Cellular Automata: Example on Random Number Reconstruction

Keywords: cellular automata, observability, reconstructibility, mobile sensors, Kalman criterion, RNG Attack

In this paper, the notions of observability and reconstructibility are defined for cellular automata. We extend the Kalman observability criterion to affine cellular automata with a time-varying output operator and apply this characterisation property to the observability and reconstructibility through mobile sensors. Then, a short and simple example is presented in order to detail the method for assessing the observability and reconstructibility of an affine cellular automata. Finally, an example where the random number stream is reconstructed from a cellular automata random number generators is considered in order to illustrate the concept of observability in the context of cybersecurity applications.

INTRODUCTION

Observability is a concept studied in systems theory that consists in looking for the extent to which the internal states of a system can be inferred from data and measurements available on the system. However, email: theo.plenet@univ-perp.fr when dealing with complex systems, our limited ability to estimate the internal state from experimentally accessible outputs severely limits their complete description. The problem lies in the ability to build sensors capable of providing measurements allowing to reconstruct the internal state of the system and thus to make it observable. For Distributed Parameter Systems (DPS) analysis and control, the sensors structures play an important role regarding the observability issue. Observability as well as controllability which are important concepts in control theory were introduced by Kalman [START_REF] Kalman | On the general theory of control systems[END_REF] for finite dimensional linear systems and well developed in the last fifty years for more general systems [START_REF] Lions | Controlabilité exacte des systèmes distribués: remarques sur la théorie générale et les applications[END_REF][START_REF] David | Controllability and stabilizability theory for linear partial differential equations: recent progress and open questions[END_REF][START_REF] Liu | Observability of complex systems[END_REF][START_REF] Amouroux | Regional observability of distributed systems[END_REF][START_REF] El | Regional observability and sensor structures[END_REF]. Their study through the concepts of sensors and actuators has also been of great interest in the automatic control community [START_REF] El | Distributed systems analysis via sensors and actuators[END_REF][START_REF] El | On the relations between actuator structures and final-constraint minimum-energy problem[END_REF]. While controllability focuses on the steering capabilities of the controlled evolution processes, observability is dealing with the ability to reconstruct the initial system state, given sufficient knowledge of the system dynamics through some output measurements.

This paper focuses on the observability problem of a distributed parameter system that is assumed to be autonomous. Motivated by some real distributed environmental phenomena (e.g. wildfires, weather, atmosphere or river pollution) we use a group of mobile robots equipped with different sensors [START_REF] Michael | Guidance of mobile actuator-plus-sensor networks for improved control and estimation of distributed parameter systems[END_REF]. Robots share information with each other and we simply call this group a network of mobile sensors. This network constitute a natural extension of sensors and offers more flexibility in collecting distributed information within its environment. A modelbased approach through trajectory optimisation (for the mobile sensors) with partial differential equation constraints (PDE, for the environment dynamical model) would lead to very complicated [START_REF] Armaou | Optimal actuator/sensor placement for linear parabolic pdes using spatial h2 norm[END_REF] -sometimes intractable -mathematical issues, particularly in the case of complex geometries and/or non linear dynamics.

Among other modelling approaches that have been developed to describe life phenomena which exhibit complex behaviours, cellular automata (CA) provide powerful models usually viewed as a counterpart of PDEs for modelling spatio-temporal systems. CA are mathematical model which is perfectly suited to complex systems containing a large number of discrete elements with local interactions, for example Ising model, fluid dynamics, traffic flow, growth of crystal [START_REF] Toffoli | A high-performance cellular-automation machine[END_REF][START_REF] Chopard | Cellular automata modeling of physical systems[END_REF][START_REF] Bagnoli | Nature of phase transitions in a probabilistic cellular automaton with two absorbing states[END_REF]. They were first introduced by [START_REF] Von Neumann | Theory of self-reproducing automata[END_REF], as a modelling tool to investigate selforganisation and self-reproduction phenomena and become increasingly attractive thanks to their ability to exhibit a wide variety of amazingly complex behaviours while offering an easiness of implementation.

The research activity regarding cellular automata was recently oriented towards systems theory when CA were presented as distributed parameter system and allowed the study of several concepts of control theory [START_REF] El | A mathematical method for control problems on cellular automata models[END_REF]. New tools have been investigated in this direction in order to obtain characterisation results that can extend or substitute the most commonly used Kalman criterion. An interesting study on controllability of CA has been carried out in [START_REF] Dridi | Recent advances in regional controllability of cellular automata[END_REF] that highlighted new ways to prove the controllability of complex systems. It mainly focused on regional controllability of Boolean CA that has been proved using Markov chains or graph theory tools [START_REF] Dridi | Markov chains approach for regional controllability of deterministic cellular automata, via boundary actions[END_REF][START_REF] Dridi | A graph theory approach for regional controllability of boolean cellular automata[END_REF]. The boundary regional controllability has also been investigated for linear (additive) Boolean CA for which some characterisation results using the Kalman condition were given.

Our interest in this paper is focused on observability as a dual notion of controllability. The purpose is to apply the above mentioned tools in order to prove the observability according to the choice of sensor structures, locations and types (mobile or fixed). We show for the 1D case, that observability of linear (affine) CA can be characterised using the observability matrix.

Although we were initially motivated by the observation of physical systems by a mobile sensor network, observability and reconstructibility can be used in other fields. In this paper, we present a rather interesting example where the observability of affine CA allow the recovery of the random number sequence generated by a random number generating cellular automaton [START_REF] Tomassini | On the generation of high-quality random numbers by two-dimensional cellular automata[END_REF]. Past and future random numbers can be deduced from some information about certain random numbers. The attacks by which the random number information is recovered are not described in this paper because the reconstruction method is independent of those. Furthermore, the choice of attack often depends on the physical or digital medium used by the random number generator.

The article is organised as follows: In section 2, the concepts of observability and reconstructibility for cellular automata are defined. Section 3 gives the observability criterion for affine CA as an extension of the rank condition established by Kalman. A complete study of affine CA by means of mobile sensors is carried out in the following section and the last section is dedicated to an important application of the concept in cybersecurity.

OBSERVABILITY AND RECONSTRUCTIBILITY FOR CELLU-LAR AUTOMATA

2.1 Cellular Automata Model Definitions for control and observation of cellular automata has already been given in [START_REF] El | A mathematical method for control problems on cellular automata models[END_REF]. Throughout this article we will reuse these definitions but for the consistency of this article we will redefine some of these. First, a cellular automaton (CA) is formulated as the quadruple A = {L, S, N , f } where L is a d-dimensional finite lattice of cells c; S denotes a discrete set of states S = {0, 1, . . . , k -1}; N is the mapping which defines the cell's neighbourhood; and f is the transition function. In this paper, the set of states S must be a field, i.e. that S is a finite commutative ring with a prime number of states. This set may also be called Z/kZ, with k a prime number of state.

Throughout this article, we will forego the local properties of CA to focus on their global properties. Therefore, we define the state s t of the whole CA at time t and the global transition function F .

s t : L → S c → s t (c) (1)
F : S L → S L s t → F (s t ) = s t+1 (2)
The evolution of the CA can now be written in a form similar to the study of linear systems:

s t+1 = F (s t ) s 0 ∈ S L ⇐⇒ s t = F t (s 0 ), t ∈ I (3)
With I = {0, 1, . . . , T } a discrete time horizon.

Sensor Model and Output Operator

To represent the measurements of a physical system modelled by a CA, we extend the previous global CA dynamical models with sensors and and output operator. Their measurements will allow us to reconstruct the initial state of the physical system using the criteria of observability and reconstructibility.

We denote q i , i ∈ 1; Q , the sensor measuring the state of several cells (we note L qi ⊂ L the set of these cells). The set of all cells measured by the sensors is denoted L q defined by:

L q = Q i=1 L qi (4)
Among all the sensors some can be considered as mobile sensors, i.e. the set of cells they measure changes as a function of time. We will then note L qi,t the set of cells measured by the sensor q i at time t and L qt the set of cells measured by all the sensors. Given this formalisation of sensors' position and motion, we are able to build an operator H t which maps, at time t, the configuration s t of the CA with the measurements θ t obtained by whole set of sensors.

H t : S L → O s t → θ t := s t | Lq t (5)
, where s t | Lq t denotes the restriction of the state s t to the set L qt of cells effectively measured at time t.

By augmenting the state representation (3) with the output θ t , the system turns into :

   s t+1 = F (s t ) θ t = H t (s t ) s 0 ∈ S L (6)

Observability and Reconstructibility

Observability, as defined by Kalman [START_REF] Emil | Mathematical description of linear dynamical systems[END_REF], determines if it is possible to reconstruct the state of a system based on the measurements obtained from one or more sensors. Observability focuses on reconstructing the initial state of the system whereas reconstructibility focuses on reconstructing the current state of the system. In the case of discrete time systems, both of these are not equivalent. With a deterministic system, observability is a more general concept as knowing the initial state implies knowing all the evolution of the system. Reconstructibility, on the other hand, is less general but can be easier to assess [START_REF] Plénet | Observability and reconstructibility of cellular automaton[END_REF].

To reconstruct the state of the system, observability and reconstructibility uses a sequence of several measurements. This vector composed of the successive output vectors (measurements) generated by the output operator H t is called an output sequence. The sequence of measurements spanning from t 0 to t T is noted Θ 0,T = (θ 0 , θ 1 , ..., θ T -1 ).

An output sequence can be computed from the initial state s 0 using the operator:

Θ T : s 0 → Θ 0,T = (H 0 (s 0 ), H 1 • F (s 0 ), . . . , H T -1 • F T -1 (s 0 )) (7)
Definition 1 (State Observability). A configuration s 0 ∈ S L of a cellular automaton A is observable by an output operator H at time T if and only if it is possible to reconstruct this initial state s 0 from the corresponding output sequence Θ 0,T .

Definition 2 (Global Observability). A cellular automaton

A is observable by an output operator H at time T if and only if all states s ∈ S L are observable by this output operator.

The definition 2 of the global observability is equivalent to the following proposition: The definition 4 of the global reconstructibility is the equivalent to the following proposition:

∀s 0 , s 0 ∈ S L , Θ T (s 0 ) = Θ T (s 0 ) =⇒ s 0 = s 0 (8)
∀s 0 , s 0 ∈ S L , Θ T (s 0 ) = Θ T (s 0 ) =⇒ F T (s 0 ) = F T (s 0 ) (9)

OBSERVABILITY CRITERION FOR AFFINE CELLULAR AU-TOMATA

This section presents the extension of the Kalman criterion, usually used to determine the observability of continuous time or discrete time linear systems, to linear cellular automata and more generally to affine CA.

Affine and Linear Cellular Automata

Before presenting the extension of the Kalman criterion to CA, we need first to express the state of a CA in the form of a state vector and then to define the properties of a CA that make it linear or affine.

To express a CA state as a state vector, the CA must have a finite lattice and its cells must be arranged in an arbitrary order. Under this assumption, an isomorphism ξ between the CA state s t and a state vector representation x t can be defined.

ξ : S L → S N s t → x t =     x 1 t x 2 t ... x N t     (10)
, where N = |L| and x i t represents the state of the cell c i at time t. In the similar way, it is possible to represent the outputs θ t as a vector denoted y t thanks to the isomorphism χ defined by :

χ : O → S Q θ t → y t =      y 1 t y 2 t ... y Q t      (11)
, where Q = |L q | and y i t represents the ith output at time t. With this change of basis, the operators F and H t become respectively F : S N → S N and Ht : S N → S Q so that :

   x t+1 = F (x t ) y t = Ht (x t ) x 0 = ξ(s 0 ), s 0 ∈ S L (12)
Definition 5 (Affine). A cellular automaton (resp. output operator) is affine if and only if F (resp. H) is an affine map. Moreover, this affine map can be written in the form of a linear map and a constant, which can be written as a matrix A (resp. C t ) and a constant η = F (0) (resp. γ t = Ht (0)). The evolution of the cellular automaton can then be written as:

   x t+1 = F (x t ) = Ax t + η y t = Ht (x t ) = C t x t + γ t x 0 = ξ(s 0 ), s 0 ∈ S L (13)
If an affine CA has a null η constant, this CA is said linear. In the case of elementary CA [START_REF] Wolfram | Statistical mechanics of cellular automata[END_REF], linear CA are called additive CA. Also, affine CA will be the complement of additive CA. For example, rule 90 and 150 will be considered linear rules, but their complementary rule (165 and 105) will be considered affine rules.

The trajectory of the CA state may be explicitely written in terms of the initial state x 0 , as:

x t+1 = A t+1 x 0 + J t η x 0 = ξ (s 0 ) , s 0 ∈ S L (14)
with J t = t k=0 A k The output sequence Θ T can also be represented in affine form using the affine forms of the transition function and the output operator. We note Y T the output sequence for T outputs where O T is the linear map and Γ T the constant vector:

Y T =     y 0 y 1 . . . y T -1     =     C 0 C 1 A . . . C T -1 A T -1     O T x 0 +     γ 0 C 1 J 0 η + γ 1 . . . C T -1 J T -2 η + γ T -1     Γ T (15) with J t = t k=0 A k .
We call O T the observability matrix as this linear map carries the injectivity property of the output sequence and therefore the observability property.

Extension of the Kalman Observability Criterion

The Kalman observability criterion [START_REF] Emil | Mathematical description of linear dynamical systems[END_REF][START_REF] Kalman | On the general theory of control systems[END_REF] is derived from the control of linear dynamical systems and proves the controllability (resp. observability) of a dynamical system when the system is controlled (observed). It has been generalised to discrete-time systems [START_REF] Sarachik | Controllability and observability of linear discrete-time systems[END_REF] and in this paper we generalise it to cellular automata.

Theorem 1 (Kalman Criterion). Let A and H t be an affine CA and affine output operator; A, C t their matrix form; and η and γ t their constants.

The pair (A, H t ) (i.e. the cellular automaton A with the output operator H t ) is observable if and only if there exists T ∈ N such that:

rank O T = rank     C 0 C 1 A .. C T -1 A T -1     = N (16)
Proof. Let A an affine CA and A and η its associated matrix and constant. Let H t be a time dependant affine output operator associated with the matrix C t and the constant γ t . Then, let x 0 ∈ S N the initial state and Y T = y 0 y 1 . . . y T -1 the output sequence generated by the output operator such that

Y T = O T x 0 + Γ T .
Considering the definition 2 of global observability, then:

(A, H t ) is observable ⇐⇒ ∀s 0 , s 0 ∈ S L , Θ T (s 0 ) = Θ T (s 0 ) =⇒ s 0 = s 0 ⇐⇒ ∀x 0 , x 0 ∈ S N , O T x 0 + Γ T = O T x 0 + Γ T =⇒ x 0 = x 0 ⇐⇒ ∀x 0 , x 0 ∈ S N , O T (x 0 -x 0 ) = 0 =⇒ (x 0 -x 0 ) = 0 ⇐⇒ ker O T = {0} ⇐⇒ rank O T = dim O T -dim(ker O T ) = N
In linear algebra, the Cayley-Hamilton theorem states that any square matrix over a commutative ring (in our case S) satisfies its characteristic equation. It can be coupled with the Kalman theorem here above to give an upper bound on the time horizon T . Proposition 1. Suppose a CA observed by a time invariant output operator C (i.e. by a static sensor), the observability matrix O T is of size N × Q.T . For the matrix O T to be of full column rank, the time horizon T has to be bounded by:

N Q ≤ T ≤ N (17)
Proof. The two inequalities are proven by the following:

• T ≤ N : The Cayley-Hamilton theorem guarantees that A N is a linear combination of lower powers, the rank of O T will not increase beyond T = N.

• T ≥ N/Q : For O T to have a rank of N , it needs at least N rows and columns, thus Q.T ≥ N .

In the case of a mobile sensor (i.e. a time variant output operator C t ), only the lower bound of the inequation (17) stands true. The Cayley-Hamilton theorem does not apply because

C T A T is a linear combination of C T + C T A + • • • + C T A T -1 and not of C 0 + C 1 A + • • • + C T -1 A T -1
Corollary 1. If the Kalman criterion is verified, then it is possible to reconstruct the initial state by inverting the observability matrix. Indeed, based on the formulation (15) we obtain:

x 0 = O † T (Y T -Γ T ) (18)
Proof. Consider an affine CA A observable by an affine output operator H t such that ∀x 0 ∈ S N , Y T = O T x 0 + Γ T and rank O T = N . To simplify the notations, we shall simply note O and Γ to respectively represent O T and Γ T .

As rank O = N , it means that it exists P such that P O = I (but not necessarily OP = I because O is full column rank not full row rank). We can find P = O † by computing the pseudo-inverse of O. Using the equation [START_REF] Kalman | On the general theory of control systems[END_REF] we find that:

Y T = Ox 0 + Γ ⇐⇒ O † (Y T -Γ) = O † Ox 0 ⇐⇒ O † (Y T -Γ) = x 0 As O is full column rank, O † = (O t O) -1 O t . If O is square then O † = O -1 .
In the case of linear systems, observability and reconstructibility are equivalent concepts [START_REF] Van Willigenburg | Linear systems theory revisited[END_REF]. The Kalman criterion ensure observability, however there are some systems which are reconstructible but not observable [START_REF] Plénet | Observability and reconstructibility of cellular automaton[END_REF], for this reason we propose a new theorem which assesses the reconstructibility of affine CA.

Theorem 2 (Reconstructibility Criterion). Let A and H be an affine CA and affine output operator; A, C their matrix form; and η and γ their constants.

The pair (A, H) (i.e. the cellular automaton A with the output operator H) is reconstructible if and only if there exists T ∈ N such that:

ker O T ⊂ ker A T (19)
If the CA is reversible [START_REF] Kari | Reversible cellular automata[END_REF] then A T is full rank thus reconstructibility is equivalent to observability. Indeed, ker O T ⊂ ker A T = {0} ⇐⇒ rank O T = N .

Proof. Let A an affine CA and A and η its associated matrix and constant. Let H t be a time dependant affine output operator associated to the matrix C t and the constant γ t . Then, let x 0 ∈ S N be the initial state and Y T = y 0 y 1 . . . y T -1 the output sequence generated by the output operator such that Y T = O T x 0 + Γ T .

Consider the definition 4 of the global observability, then:

(A, H t ) is reconstructible ⇐⇒ ∀s 0 , s 0 ∈ S L , Θ T (s 0 ) = Θ T (s 0 ) =⇒ F T (s 0 ) = F T (s 0 ) ⇐⇒ ∀x 0 , x 0 ∈ S N , O T x 0 + Γ T = O T x 0 + Γ T =⇒ A T x 0 + J T -1 η = A T x 0 + J T -1 η ⇐⇒ ∀x 0 , x 0 ∈ S N , O T (x 0 -x 0 ) = 0 =⇒ A T (x 0 -x 0 ) = 0 ⇐⇒ ker O T ⊂ ker A T Corollary 2.
If the reconstructibility criterion is verified, then it is possible to find a matrix R such that:

x T = R(Y T -Γ T ) + J T -1 η (20)
Proof. Consider an affine CA A (with a matrix A and a constant η) reconstructible by an affine output operator H t such that Y T = O T x 0 + Γ T and ker O T ⊂ ker A T . As ker O T ⊂ ker A T , it means there exists a matrix R such that A T = RO T . With this property, we can find that:

Y T = O T x 0 + Γ T ⇐⇒ R(Y T -Γ T ) = RO T x 0 ⇐⇒ R(Y T -Γ T ) + J T -1 η = A T x 0 + J T -1 η ⇐⇒ x T = R(Y T -Γ T ) + J T -1 η

OBSERVATION OF AFFINE CELLULAR AUTOMATA THROUGH MOBILE SENSORS

In this section, a simple and didactic example will be presented, it will allow to detail the operations necessary to assess the observability or the reconstructibility for cellular automata. For this purpose, the CA studied will have only one dimension and few cells in order not to overload the calculations. This CA will not have a physical representation nor a numerical utility but the next section will present another example with a numerical utility but without the detail of the calculations. Let us consider the following one-dimensional cellular automaton defined by:

• L = {0, 1, 2, 3, 4} • S = {0, 1, 2} • N : c i → {c i-1 , c i , c i+1 } with periodic boundaries so c -1 = c 4 and c 5 = c 0 . • f : s t (N (c i )) → s t (c i-1 ) + 2s t (c i ) + s t (c i+1 ) + 1
Then let us consider two output operators H and H . Both of these will observe one cell at a time, but H represents a mobile sensor (i.e. L q varying over time) while H represents a stationary sensor. The mobile sensor measure one cell and moves to the right by one cell at each time step: at t = 0 it measures cell c 0 , at t = 3 cell c 3 and at t = 5 cell c 0 (because of the periodic boundary conditions).

• Mobile Sensor: L qt = {c t mod 5 } and H : s t → s t (c t mod 5 ) + 2 0 1 2 2 0 2 2 2 1 0

1 0 2 2 1 1 1 1 2 0 1 2 0 0 1 0 0 0 2 1 2 1 0 0 2 2 2 2 0 1 FIGURE 2
Evolution of the cellular automaton over 8 time steps from the initial configuration 01220| 3 .

• Stationary Sensor: L q = {c 0 } and H : s t → s t (c 0 ) + 2

From the equations ( 10) and ( 11) and the usual order of the cells (i.e.

x i t = s t (c i )), the state system ( 12) can be written with :

F (x t ) =        2x 0 t + x 1 t + x 4 t + 1 x 0 t + 2x 1 t + x 2 t + 1 x 1 t + 2x 2 t + x 3 t + 1 x 2 t + 2x 3 t + x 4 t + 1 x 0 t + x 3 t + 2x 4 t + 1        Ht (x t ) = x t t + 2 and H (x t ) = x 0 t + 2
The transition function F is an affine map, so it can be written in an affine form with a square matrix A and a constant vector η, which leads to:

A =        2 1 0 0 1 1 2 1 0 0 0 1 2 1 0 0 0 1 2 1 1 0 0 1 2        and η =        1 1 1 1 1       
The two output operators H and H being affine, thus their matrix form are:

• Stationary Sensor: C = 1 0 0 0 0 and γ = 2 From the equation ( 17) which uses the Cailey-Hamilton theorem, we are able to compute that the observation horizon T = 5 because Q = 1 and N = 5. We can therefore calculate from (15) the observability matrix O T and the constant vector Γ T .

• Stationary: O

T =        C C A C A 2 C A 3 C A 4        =        1 0 0 0 0 2 1 0 0 1 0 1 1 1 1 2 0 1 1 0 1 0 0 0 0        , Γ T =        2 0 1 2 0        • Mobile: O T =        C 0 C 1 A C 2 A 2 C 3 A 3 C 4 A 4        =        1 0 0 0 0 1 2 1 0 0 1 1 0 1 1 1 1 0 2 0 0 0 0 0 1        , Γ T =        2 0 1 2 0       
The mobile sensor ensures the observability in a time T because the matrix O T is full rank. On the contrary, the stationary sensor does not because the rank of the matrix O T is not 5. Since observability is not verified at time T , the time horizon T should be increased as long as it respects the inequality [START_REF] Kari | Reversible cellular automata[END_REF]. In our case, there is only one possibility for T , the next operation would be to assess the reconstructibility using [START_REF] Lions | Controlabilité exacte des systèmes distribués: remarques sur la théorie générale et les applications[END_REF]. However, this would be pointless in this case because the CA is reversible (rank A = 5) and observability and reconstructibility are equivalent in this case. As the mobile sensor ensures observability, the initial state can be reconstructed using the corollary ( 18) from the measurements made by the sensor. As an example, we will reconstruct the initial state 01020| 3 as presented in figure 3 whose output sequence is

0 1 0 2 0 2 0 1 2 0 2 1 2 0 2 2 1 0 2 1 1 2 1 0 1 0 1 2 0 1 t = 0 t = 1 t = 2 t = 3 t = 4 t = 5 c 0 c 1 c 2 c 3 c 4
Y T = 2 2 1 1 0 t .
We start by finding O † T and then calculate x 0 . We should find x 0 = 0 1 0 2 0 t .

As O T is a square matrix we can compute the inverse instead of the pseudo-inverse. To calculate O -1 T , we will use the inverse of the determinant of O T , det(O T ) and its adjugate matrix adj(O T ).

O -1 T = det(O T ) -1 adj(O T ) = 2 -1        2 0 0 0 0 1 0 1 1 2 2 2 1 1 2 0 0 1 2 2 0 0 0 0 2        =        1 0 0 0 0 2 0 2 2 1 1 1 2 2 1 0 0 2 1 1 0 0 0 0 1       
In modular arithmetic base k, the inverse is obtained by finding b so that ab ≡ 1(mod k), yet in the field S that we have, 2 -1 = 2 because 2 × 2 ≡ 1(mod 3).

We can now find x 0 using Y T , Γ T and O -1

T . We get:

x 0 = O -1 T (Y T -Γ T ) =        1 0 0 0 0 2 0 2 2 1 1 1 2 2 1 0 0 2 1 1 0 0 0 0 1                      2 2 1 1 0        -        2 0 1 2 0               =        0 1 0 2 0       
With this example, we have shown the use of observability and reconstructibility through the Kalman criterion for a very simple example. The objective was to describe the computations in order to detail the method to assess the observability and reconstructibility of the system. In the next section, we will make an application on a real system, larger and more complex but we will not detail the calculations. For this example, we will focus on random number generators (RNG) and especially how it is possible to reconstruct the random number sequence using the observability of affine CAs. This example is particularly interesting because RNGs are increasingly used with the increase in cyber security in recent years.

APPLICATION OF OBSERVABILITY TO CYBERSECURITY

In cybersecurity, random number generator (RNG) are a crucial element in many applications [START_REF] Kinga Marton | Randomness in digital cryptography: A survey[END_REF]. They are used to secure https connections with SSL, to secure connections to wifi networks with WPA2 and many others. The robustness of RNGs depends on both the probability distribution and the predictability of the generator. It is also a source of several vulnerabilities that are grouped under the term "Random Number Generator Attack" [START_REF] Kelsey | Cryptanalytic attacks on pseudorandom number generators[END_REF] where the objective is to obtain information about the next generations of random numbers.

Cellular automata random number generators (CA RNG) have been widely studied for more than three decades [START_REF] Pal Chaudhuri | Additive cellular automata: theory and applications[END_REF]. CA have local, simple and regular interactions, so they can be easily integrated at large scales. Initially, cellular automata random number generators are onedimensional [START_REF] Pal Chaudhuri | Additive cellular automata: theory and applications[END_REF][START_REF] Peter D Hortensius | Cellular automata-based pseudorandom number generators for built-in self-test[END_REF][START_REF] Tsalides | Pseudorandom number generators for vlsi systems based on linear cellular automata[END_REF] but CA with two or more dimensions turn out to generate random numbers of better quality [START_REF] Pal Chaudhuri | Additive cellular automata: theory and applications[END_REF][START_REF] Tomassini | On the generation of high-quality random numbers by two-dimensional cellular automata[END_REF] but are more complex to set up. For that, different algorithms have been developed to build "automatically" these CA RNG [START_REF] Tomassini | On the generation of high-quality random numbers by two-dimensional cellular automata[END_REF].

In this section, we will use the observability of affine cellular automata to reconstruct past and future random numbers using information obtained by a random number generator attack. The nature of the attack, as well as the method used, does not matter in the context of applying the Kalman criterion, only the information obtained from the attack is important. The attack will be seen as a sensor that observes the state of the random number generator and therefore represented by the output operator H which will depend solely on the information obtained by the attack. Of these three examples, the first will use knowledge of a random number to deduce past and future numbers, the second will use information about a single bit of the random number and the last will be based on the binary parity of the generated random number. But we will start by presenting the CA RNG of Tomassini et al which will be the subject of our study.

Tomassini's et al Cellular Automata Random Number Generator

For this example, we will study a cellular automaton generating high quality random numbers proposed by Tomassini et al [START_REF] Tomassini | On the generation of high-quality random numbers by two-dimensional cellular automata[END_REF]. The quality of the random numbers generated by this CA RNG was evaluated according to the Diehard tests defined by Marsaglia in [START_REF] Marsaglia | Diehard: a battery of tests of randomness[END_REF] which were all passed successfully. This CA RNG is a two dimensional Boolean CA that generates a number consisting of 64 hexadecimal random digits. The CA generates a random number every 4 iterations but for the simplicity of the example, we will consider that it generates a 64 bit random number every iteration rather than a 64 hexadecimal digits random number every 4 iterations.

The CA RNG of Tomassini et al is defined as follows:

• L = {0, 1, . . . , 7} × {0, 1, . . . , 7}

• S = {0, 1}

• N : c i , j → {c i-1,j , c i,j-1 , c i,j , c i+1,j , c i,j+1 } with null boundaries so s(c -1 ) = 0 and s(c 8 ) = 0.

In their paper, Tomassini et al describe three limits: cyclic, fixed (full) and fixed (reduce). We can easily model fixed (full) and cyclic boundary conditions but the reduced version requires to model an CA of 10 × 10 but only the 8 × 8 cells of the center represents the random number. In our example, we will use the fixed (full) version with a zero value at the boundaries.

As opposed to the definition made at the beginning of the paper, the CA RNG of Tomassini et al is not uniform, i.e. the local transition function f depends on the cell position. Figure 4 describes the transition function that applies to each cell as a rule whose value is defined by the 6-bit string XCNWSE which corresponds to the following transition function: Therefore, according to the previous generic transition function, the rules 15, 31, 47 and 63 correspond respectively to the transition functions :

s t+1 (c i,j ) =X + C.s t (c i,j ) + N.s t (c i-1,j ) + W.s t (c i,j-1 ) + S.s t (c i+1,j ) + E.s t (c i,j+1 ) (21)
• st+1(ci,j) = st(ci-1,j) + st(ci,j-1) + st(ci+1,j) + st(ci,j+1)

• st+1(ci,j) = st(ci,j) + st(ci-1,j) + st(ci,j-1) + st(ci+1,j) + st(ci,j+1)

• st+1(ci,j) = 1 + st(ci-1,j) + st(ci,j-1) + st(ci+1,j) + st(ci,j+1)

• st+1(ci,j) = 1 + st(ci,j) + st(ci-1,j) + st(ci,j-1) + st(ci+1,j) + st(ci,j+1)

Although the system is not uniform, it can be represented with the state representation [START_REF] El | A mathematical method for control problems on cellular automata models[END_REF]. Therefore, the cells will be sorted by columns, such that s t (c i,j ) = x i+j×8 t . Moreover, regardless of the rules used, the cellular automaton will be affine so all other CA that respect Tomassini's definition can be studied in the same way.

In the following sections, we will present three purely theoretical attacks which aim to show a use of Kalman criterion. In each of the examples, we will present the attack and the associated output operator that allows to reconstruct the state of the system.

Single Measurement Attack

The principle of this attack is to use one of the generated random numbers to deduce the sequence of other random numbers. For that we will not use directly the Kalman criterion because the random number represents directly the state of the system and thus there is no reconstruction. However, we will use the reversibility of the cellular automaton to find random numbers generated previously.

As we consider that the attack provides us with a random number generated by the cellular automaton, we assume that this number corresponds to the measure y 0 with an identity output operator C = Id N . The attack by which this random number is obtained is not specified here (and is not essential for the explanation), but several methods exist in the literature such as intrusive hardware attack [START_REF] Samyde | On a new way to read data from memory[END_REF] or side-channel attack [START_REF] Standaert | Introduction to side-channel attacks[END_REF]. As the measurement of the state is made with the full state, the initial state is completely reconstructed from the first measurement. Therefore the state representation of the system is the following:

   x t+1 = Ax t + η y t = x t x 0 = ξ(s 0 ), s 0 ∈ S L
In an evident way the observability is assured at time 1 because rank O 1 = rank C = rank Id N = N . Therefore, it is possible to deduce the next generations of random numbers using [START_REF] Peter D Hortensius | Cellular automata-based pseudorandom number generators for built-in self-test[END_REF] x t = A t y 0 + J t-1 η. But also, because of the reversibility of the CA RNG, it is possible to invert the matrix A and deduce the previous generations of random numbers:

x 0 = A t x -t + J t-1 η ⇐⇒ x -t = A -t (x 0 -J t-1 η)
In this example, we were able, from a single random number generation, to deduce future but also past random numbers. This "vulnerability" can allow an intrusive (even destructive) hardware attack to retrieve a single random number in order to deduce the previous random numbers that have been used in critical operations.

Regular Measurement Attack

To reconstruct the random number stream, we will use partial information about the random numbers. In this example, we use only one of the 64 bits, but more bits could have been used (which could have reduce on the T measurement horizon, see proposition 1). In the same way as before, we will not specify how the bit of the random number is retrieved, only that we have a measurement at each time step.

To reconstruct the state of the system, we need only one bit of the random number at each time step. The measurement can be done on a single digit or change with time, the only information needed is the position of the measured digit at each time step. In this way, it is possible to create the operator C t which corresponds to the bit of the random number (or the cell associated with this bit) measured at time t. The operator C t is of the form :

C t = 0 . . . 0 1 0 . . . 0
, where the 1 corresponds to the measured bit. Then, we need to know the operators C t associated with the measurements y t and from there construct the observability matrix O T over a time horizon 64. The system is observable (i.e. rank O T = 64) regardless of the bit measured in the static case as well as for the different trajectories we have tried. However, it is not reasonable to test all the possible trajectories (there are 64 64 trajectories) so we will still have to verify if the system is observable with the given trajectory. Afterwards, it is possible to find the random number (i.e. the state x 0 ) and to deduce the random number stream as in the previous subsection.

Parity Attack

The objective of this attack is to reconstruct the random number sequence using only the binary parity of the random numbers. With this method, it is possible to reconstruct the initial state even if the random number information is not directly accessible. One method that seems to be feasible is to correlate the energy consumption of the system with the memory consumption [START_REF] Standaert | Introduction to side-channel attacks[END_REF].

Regardless of the method used, we assume to have access to the binary parity of the random number generated at each iteration. Therefore, the equations of state are the following:

         x t+1 = Ax t + η y t = 64 i=0 x i t x 0 = ξ(s 0 ), s 0 ∈ S L
The sum uses binary modular arithmetic. The output operator C t associated with parity is a row vector composed of N 1 which does not depend on time. From there, the observability matrix can be computed with T = 64 and it is full rank matrix. The system is observable with the parity measurement, which allows to reconstruct the initial state as well as the past and future states due to the reversibility of the CA RNG.

In this section, we have been able to reconstruct the random number stream from the information, total or partial, about the random numbers. The information obtained by making attacks on the random number generators is not described because the reconstruction of the state is independent of these methods. These attacks vary according to the hardware or digital support used by the CA RNG. The use of the Kalman criterion is therefore added after the recovery of the information by the attacks as a reconstruction of the random number stream. The purpose of the reconstruction was to show the usefulness of observability (and alternatively reconstructibility) for the reconstruction of a random number stream in a random number generator attack context. Although very efficient to reconstruct the random number stream, this method still have shortcoming: the CA RNG must be perfectly known; the random number seed (i.e. the state of the CA) must not be modified by the user during the measurement; and the CA RNG must not have non-linearity (which is not the case with the CA RNG presented by Tomassini).

CONCLUSION & PERSPECTIVES

Observability plays a fundamental role in complex systems that may describe the dynamics of a wide range of natural, technological and socioeconomic phenomena. The systems variables are completely dependent of each other due to the strong interaction between the system's components. Cellular Automata constitute one of the major computational techniques engaged for complex systems modelling. They consist of a large number of interconnected and mutually interacting components according to simple rules that give rise to complex emergent behaviours.

In this paper, we presented a method to prove the observability of affine cellular automata with linear output operators, either time-varying or not. We started by presenting a formulation of cellular automata observed by a mobile sensors network. Then we extended the Kalman criterion from discrete-time linear systems to affine cellular automata and we studied the observability of one-dimensional cellular automata with this method.

A very important application in cybersecurity where random number generator constitute a crucial element was considered in relation with observability of CA. Three theoretical attacks that show the usefulness of observability for the reconstruction of a CA random number were presented. Although the results obtained are still partial and deserve further investigations, they have shown a good efficiency to reconstruct the random number stream.

In a future work, we will generalise our observability analysis to nonlinear cellular automata and construct an associated state estimator. This estimator will make it possible to have an estimate of the state of cellular automata without having to wait for the time necessary for the inversion of the observability matrix. Such an observer would allow the use of cellular automata for control, diagnosis or general supervision purposes, with many potential applications, for instance in wildfire, pollution, or traffic monitoring or tracking problems.

FIGURE 1

 1 FIGURE 1Two sensors measuring a one-dimensional CA. Grey cells are measured by a sensor, either q1 or q2.

and γ 4 = 2 C 5

 25 = 1 0 0 0 0 and γ 5 = 2

FIGURE 3

 3 FIGURE 3 Example of CA evolution for x0 = 0 1 0 2 0 t . The time is along the vertical axis. Cells are numbered from left to right with c0 on the left and c4 on the right. Grey cells are those observed by the mobile sensor.

FIGURE 4 A 8 ×

 48 FIGURE 4 A 8 × 8 non-uniform cellular automaton random number generator proposed by Tomassini et al [29]. The color of the cells represents the transition function associated to this cell according to (21).


Théo Plénet
email: theo.plenet@univ-perp.fr

Samira El Yacoubi
email: yacoubi@univ-perp.fr

Clément Raïevsky
email: clement.raievsky@lcis.grenoble-inp.fr

Laurent Lefèvre
email: laurent.lefevre@lcis.grenoble-inp.fr

Observability and Reconstructibility of Bounded Cellular Automata

Keywords: cellular automata, observability, reconstructibility, mobile sensors, decentralized observability

The aim of this article is to provide several ways to assess the observability and the reconstructibility of bounded cellular automata. First, generic definitions for the considered cellular automata and their associated sensors are given, as well as the definitions for observability and reconstructibility of these measured dynamical systems. Criteria of observability and reconstructibility are proposed for linear and affine cellular automata through an extension of the Kalman criterion and for non-linear cellular automata from an extension of the results on observability and reconstructibility of boolean networks. A method for decentralized observability calculation is presented for non-linear cellular automata in order to reduce the algorithmic complexity. These criteria are analyzed and illustrated through several examples, either with fixed or mobile sensors. Numerical methods and related complexity issues are discussed.

Introduction

An increasing number of fundamental problems in natural and engineering applications involves complex systems consisting of a population of similar units that interact directly with their nearest neighbours. Although the microscopic rules are well defined, these systems exhibit emergent macroscopic behaviours that may be difficult to predict from the knowledge of their individual elements and their interactions [START_REF] D'andrea | Distributed control design for spatially interconnected systems[END_REF]. An important aspect of many of these systems is that measurement and control is often available at the unit level. These units can then be considered as agents with limited sensing, data processing and communication capabilities [START_REF] Bamieh | Distributed control of spatially invariant systems[END_REF]. Recent technological advances in the fields of microelectronics and network communication have greatly facilitated the practical implementations of this kind of spatially distributed systems [START_REF] Chu | Decentralized control of high-speed vehicular strings[END_REF].

In the analysis, design, and synthesis of systems, a fundamental issue is to determine 2019). This paper focuses first on the linear and affine CA where an extension of the well known Kalman criterion is given to prove theoretically their observability and reconstructibility properties. A first study was carried out [START_REF] Plénet | Observability of affine cellular automaton through mobile sensors[END_REF] where the observability for cellular automata was defined and characterised using an extension of the Kalman criterion for affine cellular automata. We go further in this paper by considering more general case and exploring other method to prove observability compared with reconstructibility issue. The second part focuses on non-linear cellular automata by applying the results of observability of Boolean networks [START_REF] Cheng | Analysis and control of boolean networks: a semi-tensor product approach[END_REF] to cellular automata. The criteria are then adjusted according to the constraints of bounded cellular automata in order to reduce the computational complexity of observability and reconstructibility. Finally, a decomposition of the observability and reconstructibility problem is presented in order to allow the study of large cellular automata despite the computational complexity.

This paper is structured as follows: In Section 2, preliminary on CA, sensors, and observability are discussed. In Section 3, some theoretical results using an extension of the Kalman condition are obtained in order to prove observability and reconstructibility properties for affine and linear CA. In Section 4, nonlinear CA are considered where the representation of the transition rule is given through a binary relation in order to focus on the global relation between CA configurations instead of working with local interactions. A numerical method to compute logical matrices representing the binary relations is given. Two examples are given in Section 5 in order to show the applicability of the observability and reconstructibility criteria in the case of traffic flow monitoring and the observation of a forest fire spread. Finally, Section 6 concludes the paper and gives some perspectives for future work.

Definition of Observability and Reconstructibility for Cellular Automata

Cellular Automata Model

Cellular automata (CA) are useful to model discrete-time distributed parameter systems (DPS). There is no universal formal description of CA and we therefore present here a general definition of a bounded cellular automata and sensors within the scope of observation and reconstruction. For the purpose of this article, we will simply refer to bounded cellular automata as cellular automata or CA. Such a definition have been given in [START_REF] El Yacoubi | A mathematical method for control problems on cellular automata models[END_REF], but was designed to investigate controllability (and more particularly regional controllability) issues. We will extend it with sensor models and output operators in order to cope with observability and reconstructibility analysis.

Definition 2.1. A bounded cellular automata is defined by a quadruple A = (L, S, N , f ) where:

• L is a d-dimensional finite lattice of cells (a generic cell will be denoted c, in the sequel) which are spatially arranged according their shape. We denote by N = |L| ∈ N the cardinal of L. • S denotes a discrete set of state S = {0, 1, . . . , k -1}. In the section 3, it will be necessary that S is a field, i.e. that S is a finite commutative ring with a prime number of states. This set may also be called Z/kZ. • N is a mapping which defines the cell's neighbourhood. This neighbourhood is usually the same for all cells but it can vary through space and time. It is given by:

N : L → L n c → N (c) = {c ′ ∈ L| c ′ -c i ≤ r} (1)
where ∥c∥ i , i ∈ {1, ∞} represents the taxicab norm (i = 1) or the infinity norm (i = ∞). These norms correspond respectively to the Von Neumann and Moore neighbourhoods of radius r. We denote by n = |N (c)| the cardinal of N (c). • f is a transition function which determine the cell's state at time t + 1 given the state of the neighbouring cells at time t. It is defined by:

f : S n → S s t (N (c)) → s t+1 (c) = f (s t (N (c))) (2)
where s t (c) represents the state of the cell c at time t and s t (N (c)) = {s t (c ′ )|c ′ ∈ N (c)} is the neighbourhood state at time t.

Remark 1. As we consider only finite lattices of cells, we need to define boundaries, that is to say the state of the cells that are directly "outside" the lattice, which will be used to compute states of the cells at the border of L. We will consider the three types of boundaries which are the most commonly used: periodic, reflective, and fixed [START_REF] El Yacoubi | Cellular automata modelling and spreadability[END_REF][START_REF] Luvalle | The effects of boundary conditions on cellular automata[END_REF].

This definition describes a CA from a local point of view, but in our case, we need a global definition to apply the results from system theory. This global definition will be given in term of the global CA configuration s t and a global transition function F which are defined as:

s t : L → S c → s t (c) (3)
F : S L → S L s t → F (s t ) = s t+1 (4)
The global evolution of the CA starting from an initial configuration s 0 is defined by the following state equation:

s t+1 = F (s t ) s 0 ∈ S L
(5) which can also be written:

s t = F t (s 0 ), s 0 ∈ S L (6)
where F t represents the t-th composition of F .

Sensor Model and Output Operator

To represent the measure of a physical system modelled by a CA, we extend the previous local and global CA dynamical models with sensors and and output operator.

Definition 2.2. We denote q i , i ∈ {1, 2, . . . , Q}, the sensor measuring the states of a set of cell L qi and q, the set of Q sensors that observes the set of cells L q ⊂ L with:

L q = Q i=1 L qi (7) Figure 1.
Two sensors measuring a one-dimensional CA. Grey cells are measured by a sensor, either q 1 or q 2 .

Remark 2. The sensor set q can contain mobile sensors, for which observed cell set can change over time. In this case, we will denote L qi,t the set of cells observed by the sensor i at time t and L qt the set of all observed cells at time t.

Given this formalisation of sensors' position and motion, we are able to build an operator which associates the state of the system with the measurements obtained by whole set of sensors.

Definition 2.3. The output operator H t maps, at each time t, the state s t of the cellular automata A to the output vector θ t ∈ O = S Lq t :

H t : S L → O s t → θ t := s t | Lq t (8)
where s t | Lq t denotes the restriction of the state s t to the set L qt of cells effectively measured at time t Remark 3. The vector composed of the successive output vectors (measurements) generated by the output operator H t is called an output sequence. The sequence of measurements spanning from t 0 to t T is noted Θ 0,T = (θ 0 , θ 1 , ..., θ T -1 ). An output sequence can be computed from the initial state s 0 using the operator:

Θ T : s 0 → Θ 0,T = (H 0 (s 0 ), H 1 • F (s 0 ), H 2 • F 2 (s 0 ), ..., H T -1 • F T -1 (s 0 )) (9)

Observability and Reconstructiblity

Observability, as defined by Kalman [START_REF] Kalman | On the general theory of control systems[END_REF][START_REF] Kalman | Mathematical description of linear dynamical systems[END_REF], determines if it is possible to reconstruct the state of a system based on the measurements obtained from one or more sensors. Observability focuses on reconstructing the initial state of the system whereas reconstructibility focuses on reconstructing the current state of the system. In the case of discrete time systems, both of these are not equivalent. With a deterministic system, observability is a more general concept as knowing the initial state implies knowing all the evolution of the system. Reconstructibility, on the other hand, is less general but can be easier to assess. Proposition 2.6. The definition 2.5 of the global observability is equivalent to the following proposition: Proposition 2.9. The definition 2.8 of the global reconstructibility is the equivalent to the following proposition:

∀s ′ 0 , s ′′ 0 ∈ S L , Θ T (s ′ 0 ) = Θ T (s ′′ 0 ) =⇒ s ′ 0 = s ′′ 0 ( 10
∀s ′ 0 , s ′′ 0 ∈ S L , Θ T (s ′ 0 ) = Θ T (s ′′ 0 ) =⇒ F T (s ′ 0 ) = F T (s ′′ 0 ) (11)

Observability and Reconstructibility for Affine Cellular Automata

This section presents the extension of the Kalman criterion, usually used to determine the observability of continuous time or discrete time linear systems, to linear cellular automata and more generally to affine CA.

Affine and Linear Automata

Before presenting the extension of the Kalman criterion to CA, we need first to express the state of a CA in the form of a state vector and to define the properties of a CA that make it linear or affine.

To express a CA configuration as a state vector, the CA must have a finite lattice and its cells must be arranged in an arbitrary order. Under this assumption, an isomorphism ξ between the CA configuration s t and a state vector representation x t can be defined. This isomorphism can be applied to the global transition function F to obtain another function F which computes x t+1 from x t such that:

F = ξ • F • ξ -1 (12)
Definition 3.1 (Affine Cellular Automata). A cellular automata is affine if and only if its transition function F is an affine map. Moreover, this affine map can be written in the form of a linear map A plus a constant η = F (0), which can therefore be written as:

x t+1 = F (x t ) = Ax t + η x 0 = ξ (s 0 ) , s 0 ∈ S L (13)
Remark 4. The trajectory of the CA state may be explicitely written in terms of the initial state x 0 , as:

x t+1 = A t+1 x 0 + J t η x 0 = ξ (s 0 ) , s 0 ∈ S L (14) with J t = t k=0 A k
Remark 5. An affine CA that has a null constant is said linear. In the theory of elementary CA [START_REF] Wolfram | Statistical mechanics of cellular automata[END_REF], linear CA are called additive CA. Also, affine CA are the complement of additive CA. For example, rules 90 and 150 are linear rules and their complementary rules (respectively 165 and 105) are affine rules.

Remark 6. It is possible to apply the same approach to output sequences: if the observation space is finite (i.e. |L q | = Q ∈ N) then there is an isomorphism χ which makes it possible to write the output sequence θ t as a vector y t . Moreover, the output operator is affine if and only if the H function (i.e. the H function composed with the χ isomorphism) is affine. The system can then be written as y t = Cx t + γ t where C t is the matrix of the linear map and γ t is the affine constant.

Definition 3.2. The output sequence Θ T can also be represented in affine form using the affine forms of the transition function and the output operator. We note Y T the output sequence for T outputs where O T is the linear map and Γ T the constant vector.

Y T =     y 0 y 1 . . . y T -1     =     C 0 C 1 A . . . C T -1 A T -1     OT x 0 +     γ 0 C 1 J 0 η + γ 1 . . . C T -1 J T -2 η + γ T -1     ΓT = O T x 0 + Γ T (15)
We call O T the observability matrix as this linear map carries the injectivity property of the output sequence and therefore the observability property.

Extension of the Kalman Criterion

The Kalman condition [START_REF] Kalman | On the general theory of control systems[END_REF][START_REF] Kalman | Mathematical description of linear dynamical systems[END_REF] was initially derived to assess the controllability (resp. observability) of continuous-time linear dynamical systems when they are controlled (resp. observed). It has been generalised to discrete-time systems [START_REF] Sarachik | Controllability and observability of linear discrete-time systems[END_REF] and this paper proposes a generalisation to cellular automata.

Theorem 3.3 (Kalman Condition).

Let A and H be an affine cellular automata and affine output operator, with associated matrices respectively denoted A and C.

The pair (A, H) (i.e. the automata A with the output operator H) is observable if and only if there exists a time T ∈ N such that:

rank O T =     C 0 C 1 A . . . C T -1 A T -1     = N (16)
In linear algebra, the Cayley-Hamilton theorem states that any square matrix over a commutative ring (in our case S) satisfies its characteristic equation. It can be coupled with the Kalman theorem here above to give an upper bound on the time horizon T .

Proposition 3.4. Suppose a CA observed by a time invariant output operator C ( i.e. by a static sensor), the observability matrix O T is of size N × Q.T . For the matrix O T to be of full column rank, the time horizon T has to be bounded by:

N Q ≤ T ≤ N (17)
Proof. The two inequalities are proven by the following:

• T ≤ N : The Cayley-Hamilton theorem guarantees that A N is a linear combination of lower powers, the rank of O T will not increase beyond T = N. • T ≥ N/Q : For O T to have a rank of N , it needs at least N rows and columns, thus Q.T ≥ N .

Remark 7. In the case of a mobile sensor (i.e. a time variant output operator C t ), only the lower bound of the inequation (17) stands true. The Cayley-Hamilton theorem does not apply because

C T A T is a linear combination of C T + C T A + • • • + C T A T -1 and not of C 0 + C 1 A + • • • + C T -1 A T -1
Proof. Let A an affine CA and A and η its associated matrix and constant. Let H t be a time dependant affine output operator associated with the matrix C t and the constant γ t . Then, let x 0 ∈ S N the initial state and Y T = y 0 y 1 . . . y T -1 the output sequence generated by the output operator such that

Y T = O T x 0 + Γ T .
Considering the definition 2.5 of global observability, then:

(A, H t ) is observable ⇐⇒ ∀s ′ 0 , s ′′ 0 ∈ S L , Θ T (s ′ 0 ) = Θ T (s ′′ 0 ) =⇒ s ′ 0 = s ′′ 0 ⇐⇒ ∀x ′ 0 , x ′′ 0 ∈ S N , O T x ′ 0 + Γ T = O T x ′′ 0 + Γ T =⇒ x ′ 0 = x ′′ 0 ⇐⇒ ∀x ′ 0 , x ′′ 0 ∈ S N , O T (x ′ 0 -x ′′ 0 ) = 0 =⇒ (x ′ 0 -x ′′ 0 ) = 0 ⇐⇒ ker O T = {0} ⇐⇒ rank O T = dim O T -dim(ker O T ) = N Corollary 3.5.
If the Kalman criterion is verified, then it is possible to reconstruct the initial state by inverting the observability matrix. Indeed, based on the formulation (15) we obtain:

x 0 = O † T (Y T -Γ T ) (18)
Proof. Consider an affine CA A observable by an affine output operator H t such that ∀x 0 ∈ S N , Y T = O T x 0 + Γ T and rank O T = N . To simplify the notations, we shall simply note O and Γ to respectively represent O T and Γ T .

As rank O = N , it means that it exists P such that P O = I (but not necessarily OP ̸ = I because O is full column rank not full row rank). We can find P = O † by computing the pseudo-inverse of O. Using the equation ( 15) we find that:

Y T = Ox 0 + Γ ⇐⇒ O † (Y T -Γ) = O † Ox 0 ⇐⇒ O † (Y T -Γ) = x 0 (19) As O is full column rank, O † = (O t O) -1 O t . If O is square then O † = O -1 .
Remark 8. In definition 2.1, one of the conditions for S to be a field is that the state number k is prime. If it is not, the inverse of a number does not necessarily exist however the inverse is required to reconstruct the initial state with corollary 3.5. Moreover, in modular arithmetic, this inverse is not computed from the usual division but from multiplication and modulo:

a -1 = b =⇒ b • a = 1 (mod k) (20)
In the case of linear systems, observability and reconstructibility are equivalent concepts [START_REF] Van Willigenburg | Linear systems theory revisited[END_REF]. The Kalman criterion ensure observability, however there are some systems which are reconstructible but not observable (See example 5.1), for this reason we propose a new theorem which assesses the reconstructibility of affine CA.

Theorem 3.6 (Reconstructibility Criterion). Let A and H be an affine CA and affine output operator; A, C their matrix form; and η and γ their constants.

The pair (A, H) (i.e. the automata A with the output operator H) is reconstructible if and only if there exists T ∈ N such that:

ker O T ⊂ ker A T (21) Remark 9. If the CA is reversible (Kari, 2005) then A T is full rank thus recon- structibility is equivalent to observability. Indeed, ker O T ⊂ ker A T = {0} ⇐⇒ rank O T = N .
Proof. Let A an affine CA and A and η its associated matrix and constant. Let H t be a time dependant affine output operator associated to the matrix C t and the constant γ t . Then, let x 0 ∈ S N be the initial state and Y T = y 0 y 1 . . . y T -1 the output sequence generated by the output operator such that

Y T = O T x 0 + Γ T .
Consider the definition 2.8 of the global observability, then:

(A, H t ) is reconstructible ⇐⇒ ∀s ′ 0 , s ′′ 0 ∈ S L , Θ T (s ′ 0 ) = Θ T (s ′′ 0 ) =⇒ F T (s ′ 0 ) = F T (s ′′ 0 ) ⇐⇒ ∀x ′ 0 , x ′′ 0 ∈ S N , O T x ′ 0 + Γ T = O T x ′′ 0 + Γ T =⇒ A T x ′ 0 + J T -1 η = A T x ′′ 0 + J T -1 η ⇐⇒ ∀x ′ 0 , x ′′ 0 ∈ S N , O T (x ′ 0 -x ′′ 0 ) = 0 =⇒ A T (x ′ 0 -x ′′ 0 ) = 0 ⇐⇒ ker O T ⊂ ker A T Corollary 3.7.
If the reconstructibility criterion is verified, then it is possible to find a matrix R such that:

x T = R(Y T -Γ T ) + J T -1 η (22)
Proof. Consider an affine CA A (with a matrix A and a constant η) reconstructible by an affine output operator

H t such that Y T = O T x 0 + Γ T and ker O T ⊂ ker A T .
As ker O T ⊂ ker A T , it means there exists a matrix R such that A T = RO T . With this property, we can find that:

Y T = O T x 0 + Γ T ⇐⇒ R(Y T -Γ T ) = RO T x 0 ⇐⇒ R(Y T -Γ T ) + J T -1 η = A T x 0 + J T -1 η ⇐⇒ x T = R(Y T -Γ T ) + J T -1 η

Numerical Method for Assessing Observability

When cellular automata are very large, it becomes necessary to use a computer to construct the A, C, and O matrices and to evaluate the rank of the observability matrix. This section presents some heuristics to numerically construct these matrices and to evaluate observability.

Before constructing the matrices, the operators ξ and χ must be determined according to the order in which the CA's cells are arranged. Any order would do but to simplify the construction of the matrices it is wise to take the usual order.

Using this method, the matrix A appears as a circulant (or a nearly circulant depending on the boundaries conditions) matrix with several diagonals that depends on the neighbourhood.

In most cases, the state of a cell is observed directly, i.e. each element of the output vector y is the state of one of the cells of the automata. If this is the case, then the matrix C has only one non-zero element in each row at the position corresponding to the observed cell.

The following matrix is designed to measure the 2 nd cell as well as the 5 th cell :

C = 0 0 1 0 0 0 0 0 0 0 0 0 1 0
Once the matrices A and C have been constructed, it is possible to calculate the matrix O from its definition. Then, the observability of the CA can be determined by computing the rank of O.

The rank of a matrix is usually calculated with Gaussian elimination [START_REF] Bunch | Triangular factorization and inversion by fast matrix multiplication[END_REF] but new and better methods exist [START_REF] Cheung | Fast matrix rank algorithms and applications[END_REF]. The algorithmic complexity of Gaussian elimination of a M ×N matrix is O(N M ω-1 ), with ω ≤ 2.38. When the Gaussian elimination is applied to the rank of the observability matrix O T of size N × Q.T , the complexity is O(QT N ω-1 ).

Observability and Reconstructibility of Non-Linear Cellular Automata

In the previous part, we have studied the observability and the reconstructibility of affine CA but this represents a very small part of the existing automata: only 16 rules out of the 256 Wolfram's elementary rules are affine.

To study non-linear cellular automata, we chose not to focus on the algebraic expression of the transition function, as we were able to do with the linear case. Indeed, this method does not allow us to study all types of automata independently of the properties of their transition function. The idea is to study the relation between configurations and not between cells.

This method has already been studied many times for the computation of the observability and reconstructibility of Boolean (Control) Networks [START_REF] Cheng | Analysis and control of boolean networks: a semi-tensor product approach[END_REF][START_REF] Laschov | Observability of boolean networks: A graphtheoretic approach[END_REF]. In this section, we adapt these formulations to bounded cellular automata and propose numerical methods to verify their observability and reconstructibility. Moreover, we present a method for computing observability in a decentralized way that aims at reducing the algorithmic complexity at the expense of the number of sensors.

Binary Relation Representation

Bounded cellular automata can be seen as a particular case of Boolean networks [START_REF] Gershenson | Classification of random boolean networks[END_REF] where the topology of the network depends on the position of the cell (or variable) and the transition function does not depend on the cell (for homogeneous CA only). This great similarity between the two representations makes it possible to apply the observability and reconstructibility results of BN to CA, but their differences permit to adapt these theorems in order to reduce their algorithmic complexity.

Cheng et al. developed an algebraic state representation for BCN that uses the semi-tensor product [START_REF] Cheng | Analysis and control of boolean networks: a semi-tensor product approach[END_REF], a matrix product derived from the Kronecker product. This method allows to have a state representation for nonlinear cellular automata as we have done in the previous section.

Definition 4.1 (Semi-tensor product [START_REF] Cheng | Semi-tensor product of matrices and its applications to dynamic systems[END_REF]). Let A ∈ M p×q and B ∈ M m×n . The semi-tensor product is define by:

A ⋉ B = A(B ⊗ I k ), if q = km A ⋉ B = (A ⊗ I k )B, if kq = m
where ⊗ is the Kronecker product. Definition 4.2 [START_REF] Cheng | Analysis and control of boolean networks: a semi-tensor product approach[END_REF]). Let A and H be a cellular automata and output operator, with associated binary matrices respectively denoted M F and M H .

The evolution of the CA can be written as :

x t+1 = M F ⋉ x t y t = M H ⋉ x t (23) with x t = x 1 t ⋉ • • • ⋉ x N t
With this representation, the observability matrix M O can be constructed in a similar way to the definition (3.2) by replacing the usual matrix product by the semi-tensor product. Once the observability matrix M O is obtained, we can study its injectivity property by looking at the different columns rather than the rank of the matrix.

Theorem 4.3 [START_REF] Laschov | Observability of boolean networks: A graphtheoretic approach[END_REF]). Let A and H be a cellular automata and output operator, with associated binary matrices respectively denoted M F and M H .

The pair (A, H) is observable if and only if there exists a time T ∈ N such that no two columns of the observability matrix M O are identicals.

The binary matrix M F describes the behavior of the CA at the configuration level, in other words M F plays the role of the adjacency matrix of the state transition diagram of the CA [START_REF] Laschov | Observability of boolean networks: A graphtheoretic approach[END_REF][START_REF] Martin | Algebraic properties of cellular automata[END_REF]. Thus the matrix M F is not of size N × N as for affine CA but S N × S N , where N is the number of cells and S N the number of configurations. This exponential size of the matrix makes it difficult to apply to CA with a large number of cells.

We have the possibility to reduce the size of the matrices by using sparse matrices [START_REF] Buluç | Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks[END_REF], an advantageous formulation (in terms of memory and algorithmic complexity) for matrices that have few non-zero elements. Moreover, by using the Yale format (or Compressed Row Format) observability can be evaluated by checking that a 1D array does not contain duplicates. Therefore, the algorithmic complexity to evaluate the observability of a CA with S N configurations is O(S N ). Laschov et al. have shown that in the general case, the computation of the observability of BN is a NP-Hard problem [START_REF] Laschov | Observability of boolean networks: A graphtheoretic approach[END_REF], so without simplification on the CA (as we have done with affine CA) it will be difficult (or even impossible) to find an algorithm with polynomial complexity.

Even using sparse matrices, the calculation of observability or reconstructibility for cellular automata becomes difficult when these exceed a hundred cells. The objective is therefore to benefit from some properties of cellular automata to simplify these computations of observability and reconstructibility. The first property concerns in particular cellular automata with constraints on the initial configurations. Thus, many initial configurations can be excluded from the observability computation because they are impossible in the concerned application case. If we take the example of section 5.2, as we know the topology of the forest and that the fire can only start on one cell of the CA, the number of initial configurations to study goes from 4 225 to only 158. The second property takes advantage of the ease of distribution of the computation of the CA [START_REF] Millán | Performance analysis and comparison of cellular automata gpu implementations[END_REF]. Indeed, when the number of cells is large, it is more efficient to compute several times the local function f than the global function F once. Thus the computation of the observability matrix is no longer performed from the matrix product of F and H but from a large number of simulations.

In order to benefit from those properties, we propose a definition of observability and reconstructibility based on binary relations. These allow to associate two elements, here the initial configuration s 0 (or current configuration s T if we study the reconstructibility) and the associated output sequence Θ T (s 0 ). When we come to build this binary relation, we add the pair (s 0 , Θ T (s 0 )) only if the initial configuration s 0 is part of the initial configurations to study. In this formulation, the calculation of Θ T can be done by simulation or by calculation using F and H according to what is more efficient. Therefore, we can define the observability binary relation R Θ and the reconstructibility binary relation RΘ by: Definition 4.4. The observability and reconstructibility binary relation R Θ and RΘ associated to the output sequence Θ T is defined as follows: R Θ = {(s 0 , Θ 0,T )|s 0 ∈ W and Θ 0,T = Θ T (s 0 )} (24) RΘ = {(s T , Θ 0,T )|s 0 ∈ W and Θ 0,T = Θ T (s 0 ) and s T = F T (s 0 )} ( 25)

where W ⊂ S L represents the set of admissible initial configurations.

Remark Proof. For the observability condition, the theorem follows directly from proposition 2.6 which represents the writing of the injectivity of Θ and R Θ is the relational writing of Θ.

For the reconstructibility condition, the theorem follows directly from proposition 2.9 which can be written as follows:

(11) ⇐⇒ ∀s ′ 0 , s ′′ 0 ∈ W, Θ T (s ′ 0 ) = Θ T (s ′′ 0 ) =⇒ s ′ T = s ′′ T ⇐⇒ ∀s ′ T , s ′′ T ∈ F T (W), RΘ (s ′ T ) = RΘ (s ′′ T ) =⇒ s ′ T = s ′′ T ⇐⇒ RΘ is injective
In order to numerically verify the observability or reconstructibility of the CA, we must first construct the relations R Θ and RΘ and then verify their injectivity. Therefore we propose the algorithm 1 that allows to construct simulataneously the relations R Θ and RΘ but also to check their injectivity during their construction.

In order to construct the observability relation, the output sequence is computed for each of the possible initial configurations s 0 ∈ W. However, to obtain the output sequence Θ T (s 0 ) we need the configurations from s 0 to s T -1 , so we can take advantage of s T -1 to compute s T in order to build the reconstructibility relation. As for the evaluation of the injectivity, we use a specific data strcuture called Hashmap to record the relations R Θ and RΘ . This type of data structure allows to store a value with a key and to guarantee the uniqueness of the key. In this manner, by using the output sequence as a key and the initial configuration (or current configuration) as a value we are able to verify two things. The first is to make sure that each output sequence is associated to only one configuration and thus to check the injectivity of the observability and reconstructibility relations. The second is to be able to easily find the configuration related to the output sequence and therefore know the initial configuration when measurements are performed on the system.

Algorithm 1: Verification of observability and reconstructibility of (A, H)

AssessObsRec (W, F, Θ T ) inputs : A set of
∈ W do (Θ 0,T , s T -1 ) ← Θ T (s 0 ); s T ← F (s T -1 ); if Obs[Θ 0,T ] already exists then is Obs ← false; else Obs[Θ 0,T ] ← s 0 ; if Rec[Θ 0,T ] already exists then if Rec[Θ 0,T ] ̸ = s T then is Rec ← false; else Rec[Θ 0,T ] ← s T ;
return Obs, Rec, is Obs, is Rec

This algorithm is separated into two parts, the first where the output sequence and the current configuration are computed and the second where these values are stored in the Hashmap. Thus the first part has a complexity of O(T G) where T is the time horizon and G is the complexity of the global transition function F , then the second part has a complexity of O(1). Thus, the total algorithmic complexity is O(W T G) where W is the number of admissible configurations.

If we consider that all initial configurations are studied (i.e. W = S L ) and that F has linear complexity with respect to the number of cells N , because the local function f is applied separately to each cell, (so logarithmic with respect to the number of configurations S N ) then the complexity of the alogrithm is O(S N T N log(S)).

Compared to the algorithm that verifies observability for affine CAs presented in section 3.3, this algorithm has a greater complexity. The algorithmic complexity for verifying observability is polynomial for affine CA O(T QN ω-1 ) and exponential for non-linear CA O(S N T N log(S)), with N representing the number of cells, Q the number of sensors, S the number of states and T the time horizon.

Decomposition of the Observability and Reconstructibility Problem

In order to be able to use the results of the previous subsection, we need to find a method that will drastically reduce the algorithmic complexity necessary to compute the observability. As cellular automata are not very connected (few links between cells), it is possible to decompose the observability problem into smaller ones which would drastically reduce the algorithmic complexity. In this way, the observability is computed only on a part of the CA which allows to move the complexity factor from the size of the CA to the size of this part. To do this, sensors and subdivisions must be judiciously placed to ensure observability or reconstructibility at any point in the cellular automata.

The subdivisions do not represent a whole CA and are no longer isolated, so the boundaries are cells of the CA and do not respect the rules on boundaries that we defined at the beginning of the paper. We can consider that these boundaries take random states at each time step, in this way, we have to define a new notion of observability and reconstructibility for automata with randomly valued boundaries. On the observation horizon T, the boundaries will have a sequence of values called boundary trajectory and it will be necessary to check the observability for each trajectory therefore if the output sequence and the boundary trajectory are known then the initial state of the subdivision can be reconstructed.

Theorem 4.6. A cellular automata A with randomly valued boundaries is observable (reconstructible) by an output operator H at time T if and only if the cellular automata is observable (reconstructible) for every boundary trajectories.

To ensure the observability of a part of CA, it is necessary to know the value of boundary trajectory, so we must place sensors directly outside the CA but also inside it. If we ensure the observability only for a part of the CA we speak then of regional observability [START_REF] Fekih | Regional analysis of a class of cellular automata models[END_REF]. But in our case, we will study the observability of the whole CA through multiple parts of it.

Remark 11. This method works very well for one-dimensional automata because the size of the boundary is independent of the number of cells in the CA, there are always 2 boundaries. However, in two dimensions (or more) the number of boundary cells increases greatly. Indeed, to obtain the observability of a 3 × 3 CA it is necessary to know the state of the 16 boundary cells (i.e. more than the CA itself).

For one-dimensional CA, the sensors can be placed directly on the edges of the CA of the sub-observer and thus act as a sensor for the sub-observer and as a boundary cell sensor for the neighbouring sub-observers (see figure 2). In this way, each sensor has the dual purpose of measuring the boundary cells and estimating the cells of the CA. Of course, if this sensor topology is not sufficient to ensure observability or reconstructibility, other sensors can be added inside the sub-observer but their only purpose will be to estimate the state of the sub-observer. This method significantly reduces the complexity of the observability of one-dimensional CA because the subdivision reduces the number of cells whose observability we seek to verify. If we split a CA of size N in k equal parts then the number of initial configuration is not S N but S N k but we also have to evaluate for the 2 S T limit trajectories so there are S N k × 2 S T . However, if the sub-observers are not of the same size, then observability must be checked independently for each sub-observer size.

Example on Several Application

In this section, we will apply the criteria of observability and reconstructibility to two separate examples. For the first example, we will use a Wolfram's non-linear rule which is used to model a traffic flow: the rule 184. This rule also makes it possible to show, on certain systems, that observability is difficult to ensure in contrast to reconstructibility which may be simpler. In the second example we study the observability problem for a two-dimensional forest fire spread model. This example will also show that observability may sometimes be easier to ensure with mobile sensors.

Traffic Flow Example

Elementary Rule 184 is one of the most used of Wolfram's elementary rules. It is mainly used to model in a simple way the traffic flows [START_REF] Maerivoet | Cellular automata models of road traffic[END_REF] and the particle deposition [START_REF] Krug | Universality classes for deterministic surface growth[END_REF]. The model is deterministic, boolean and one-dimensional. For this example, we will study the elementary rule 184 which is a one-dimensional Boolean cellular automata. Because of the algorithmic complexity of the relational method we will only consider a few cells. We will consider 10 cells for a total of 1024 configurations and we will use periodic boundaries, so the CA can be defined as:

• L = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} • S = {0, 1} • N : c → {c -1, c, c + 1} with respect to the periodic boundaries, thus N (0) = {0, 1, 9} and N (9) = {0, 8, 9}. • f : {s t (c -1), s t (c), s t (c + 1)} → s t (c -1) + s t (c -1) • s t (c) + s t (c) • s t (c + 1) with
respect to the modular arithmetic of S.

Since the transition function of this CA is non-linear, its observability cannot be assessed with the Kalman criterion.

This CA poses another problem regarding observability: it cannot be evaluated with few sensors. Indeed, to differentiate the two initial configurations presented in figure 4, it would be necessary to observe 2 of the 3 cells that are non-zero among the two initial configurations. This problem can be shifted over the whole CA and it would thus be necessary to place a sensor every two cells to resolve this issue. Conversely, this convergence of two initial configurations does not pose any difficulty with respect to the reconstructibility of the cellular automata. Because of this, we won't study the observability but focus on finding a sensor to ensure the reconstructibility.

We have the intuition that reconstructibility can be provided by a single sensor, wherever it is. Indeed, because the system propagates in one direction only, a sensor could see all the non-zero states pass and deduce their future positions. To carry on with the traffic flow analogy, this sensor could be a tollbooth which, at a certain moment, measures all the cars. In this case, if the cell 0 is observed by the sensor then the output operator is defined as:

• L q = {0} • H : s t → s t (0)
To verify the reconstructibility of the cellular automaton, we will use algorithm 1 in order to construct the reconstructibility relation R T as well as to verify its injectivity. For this application case, there is no constraint on the configurations since each location can be occupied by a car or not, therefore W = S L . We cannot apply the Cayley-Hamilton theorem, thus we start assessing the reconstructibility with a minimum time horizon T = 1 and will increase it gradually until the reconstructibility is verified. In addition, we modify the algorithm 1 so that it counts the number of unobservable and unreconstructible configurations and plot this number as a function of the time horizon T in figure 5. Finally, the system is reconstructable from T = 14. The number of unreconstructible configurations converges to 0 while the number of unobservable configurations is not zero. Reconstructibility is well ensured at time 14 but not observability. The reduction in the number of configurations between time 9 and 10 is specific to the system, it is the minimum time necessary for the sensor to measure the impact of all the cells through the measured cell. Indeed, with 10 cells and periodic boundaries, it takes 10 time steps for the cell on the far right to have an impact on the cell on the far left (the measured cell).

Finally, we aim to extend our model to observe a larger road network. For this, we intend to observe a CA of 1, 000 cells but the algorithmic complexity of algorithm 1 is far too important. Therefore, we study a CA of size 1000 but using 100 sub-observers of size 10. We use the sensor topology shown in Figure 2, one sensor at each end of the lattice. In the same way as for the study of reconstructibility, we have no constraint on the time horizon T from which the CA is reconstructible for randomly valued boundaries. To do this, we start with a low time horizon T and increase it gradually until reconstructibility is ensured. By doing simulations, we verify that the reconstructibility is assessed for T = 7.

This method with the sub-observers allowed to ensure the reconstructibility for the whole CA which would have been impossible without it. Indeed, with 1000 cells the number of operations to evaluate the reconstructibility is 2 1000 with the usual method against 2 10 • 2 2 * 7 = 2 24 for the reconstructibility with the sub-observers.

Forest Fire Example

In this example, we will study the observability and reconstructibility property for a two-dimensional cellular automata. To observe the state of this system, we will use a single sensor that can move. This type of sensor can be similar to a drone that flies over an environment and perceives only part of it. For this second example we will study the observability and reconstructibility of a two-dimensional CA of size 15 × 15 whose goal is to model the spread of a fire in a non homogeneous forest.

The state of the cells represents the state of the forest, which can correspond to four different states: an empty cell, a forest cell, a burning forest cell and a burned forest cell. The behavior of the cells is quite simple: an empty cell does not change state; a forest cell becomes a burning forest cell if at least one of its neighbors is a burning forest cell; a burning forest cell becomes a burned forest cell; and a burned forest cell does not change state. This behavior can be represented by the figure 6. The cellular automata is defined as follows:

• L = {0, 1, 2, . . . , 13, 14} • S = {0, 1, 2, 3}
• N is the Von Neumann neighbourhood of radius 1 and we consider fixed to 0 boundaries, thus:

N : c → N (c) = {c ′ ∈ L| c ′ -c 1 ≤ 1}
The presented CA is non-linear, so we will use the results of part 4 to prove observability. However, due to the number of configurations, it is not possible to check the observability, so we will drastically reduce the number of possible initial configurations while respecting the coherence with the model.

In the case of the forest fire spread, we can consider that the initial configuration represents a forest (i.e. neither burning nor burned forest) and only one burning forest cell to represent the ignition point of the fire. Moreover, the topology of the forest is known, i.e. only one initial configuration of forest will be studied. For our example, we will use the forest presented on figure 7 with 157 forest cells and 68 empty cells. By making these simplifications, the number of possible initial configurations increases from 4 225 to 158. Some parts of the forest are not connected to the rest and therefore cannot be ignited. In order to determine the state of these parts, these cells must be directly measured by the sensors. For the chosen topology, there are 4 cells isolated from the rest of the forest which would require 4 sensors but a single measurement would be enough to detect the fire in these areas. The mobile sensors could measure the state of these cells and directly go and measure other cells. For this kind of property, mobile sensors seem to be more efficient. Indeed, if we consider a random distribution of 15 sensors then the average number of unobservable configurations is 18.2 for mobile sensors (the position is determined randomly at each time step) against 47.4 for fixed sensors. Although we have not been able to find a trajectory for mobile sensors that ensures observability, they seem to be more efficient than fixed sensors.

Finding positions or trajectories for the sensor network to observe the system is a complex problem as there is no "simple" method to produce an observer from the system and the constraints. Moreover, for given constraints there is not necessarily a position or trajectory that ensures observability or reconstructibility.

The calculation of a trajectory is more complex than the calculation of a position because it is a question of finding a position per sensor and per time step. Moreover, new constraints are added such as obstacle avoidance or physical constraints of speed or acceleration. Some researchers are directly studying the problem of observability with mobile sensors. Noticeably Demetriou et al [START_REF] Demetriou | Guidance of mobile actuator-plus-sensor networks for improved control and estimation of distributed parameter systems[END_REF][START_REF] Demetriou | Estimation of spatially distributed processes using mobile spatially distributed sensor network[END_REF] or Hussein et al [START_REF] Hussein | Effective coverage control for mobile sensor networks with guaranteed collision avoidance[END_REF] are considering networks of mobile sensors. Related problems occurred when mobile sensors (or actuators) are considered such as obstacle avoidance or formation coordination to get maximum coverage.

Conclusion

At the beginning of this article, the notions of observability and reconstructibility were defined for cellular automata. They have been presented theoretically for finitestate and finite-lattice cellular automata. They also allow the observation of cellular automata with a network of static and mobile sensors.

Two criteria were then presented to assess observability and reconstructibility of CA. The first one applies only to affine CA and derives from an extension of the Kalman criterion. The second one derives from results on Boolean networks and applies more generally to CA, at the cost of a greater complexity. Despite its greater complexity, this second criterion has been utilized in conjonction with CA-specific constraints to, first, design an algorithm that verifies observability and reconstructibility, and, second, to decompose the observability and reconstructiblity problems and solve them for CA with many more cells.

Finally, the observability and reconstructibility criteria have been applied to two very different examples. The first one is the elementary rule 184 use to model traffic flow. We have shown the benefit of recontructibility compare to observability for this particular example as well as the decomposition of the reconstructibility problem for a thousand cells. The second example is a two dimensional forest fire spread model in which we have address the observability problem by largely reducing the number of inital configurations and by using a network of mobile sensors.

This work on observability and reconstructibility will make it possible in the future to develop a systemic method for constructing an observer. For the moment, observers are found by trial and error, which, along with the complexity of relational methods, poses problems of computation time. The observability and reconstructibility criteria can also be used to coordinate a sensor network by using the classical method such predictive controller at the cost of a higher computation time or by using a decentralized method such as the multi agent paradigm at the cost of optimality loss.

Figure 2 .

 2 Figure 2. A one-dimensional CA subdivided into 3 parts. Grey cells are measured by a sensor.

Figure 3 .

 3 Figure 3. Rule 184 interpreted as a simulation of traffic flow. Each 1 cell corresponds to a vehicle, and each vehicle moves forward only if it has open space in front of it. Image from David Epstein at English Wikipedia

Figure 4 .

 4 Figure 4. Evolution of the rule 184 for two similar initial configurations. Time is going down on the vertical axis.

Figure 5 .

 5 Figure 5. Number of unobservable/unreconstructible configurations as a function of the time horizon T .

Figure 6 .

 6 Figure 6. State Transition Diagram for the Cell.

Figure 7 .

 7 Figure 7. Topology of the forest without fire outbreak.

  Definition 2.4 (State Observability). A state s 0 ∈ S L of a cellular automata A is observable by an output operator H at time T if and only if it is possible to reconstruct this initial state s 0 from the corresponding output sequence Θ 0,T .

	Definition 2.5 (Global Observability). A cellular automata A is observable by an
	output operator H at time T if and only if all states s ∈ S L are observable by this
	output operator.

)

  Definition 2.7 (State Reconstructiblity). A state s T ∈ S L of a cellular automata A is reconstructible by an output operator H at time T if and only if it is possible to reconstruct the current state s T from the corresponding output sequence Θ 0,T . Definition 2.8 (Global Reconstructiblity). A cellular automata A is reconstructible by an output operator H at time T if and only if all states s ∈ S L are reconstructible by this output operator.

  10. If we consider the whole set of initial configurations (i.e. W = S L ) then R Θ , M O , Θ T represent the same relation except that R Θ is in set form and M O in binary matrix form.

Theorem 4.5. A cellular automata A is observable (resp. reconstructible) by an output operator H at time T if and only if the binary relation R Θ (resp. RΘ ) is injective.

  admissible initial configuration W; a global transition function F ; an output sequence operator Θ T output: The observability Hashmap Obs; the reconstructibility Hashmap Rec; the observability status is Obs; the reconstructibility status is Rec Declare Obs and Rec as two empty Hashmap; Declare is Obs and is Rec as two boolean variables initialized to true; foreach s 0

Acknowledgments

This work was supported by the Doctoral School 305 of the University of Perpignan Via Domitia.

Data availability statement

Data sharing is not applicable to this article as no new data were created or analyzed in this study.


M De Anda Villa
email: manuel.andavilla@insp.jussieu.fr

A Lévy
email: levy@insp.jussieu.fr

J Gaudin

R Bouillaud

D Descamps

B Dorado

N Fedorov

R Grisenti

M Hatifi

H Jouin

E Lamour

S Macé

P Martin

S Petit

C Prigent

R Sobierajski

S Steydli

M Trassinelli

A Wawro

D Vernhet

Ultrafast laser induced structural dynamics probed by time-resolved photoelectron spectroscopy

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.

Synopsis

This work aims to study laser-induced lattice dynamics when there is strong electron-lattice temperature non-equilibrium for which the material properties are poorly known. The proposed experimental technique is timeresolved photoelectron spectroscopy (Tr-PES). The main challenges of such technique are the superposition of pump and probe spectra and the distortion of the probe spectra due to the interaction with pump-induced electrons, called space charge effect (SCE). We strongly reduced this effect by tuning the 100eV XUV beamline we have developed, enabling us to investigate Copper samples.

When ultra-short laser pulses induce a non equilibrium regine of the electron-lattice temperature, theoretical description is difficult due to the limited knowledge of material properties in these conditions [1], including the electron-phonon coupling factor, the electronic and ionic thermal conductivities, and the electron heat capacity. In this context, time-resolved photoelectron spectroscopy (Tr-PES) experiments may help to improve our understanding of the physical processes and material properties in this regime.

The excitation and relaxation of matter can be diagnosed by studying the time evolution of their PES spectra, which is influenced by the lattice state/temperature. However, such a pump/probe experiment, based on the detection of probe-induced photoelectron spectra, is technically challenging due to the presence of a pump-induced high flux of photoelectrons that can cause a loss of information by overlapping and/or interacting with the probe electrons, distorting the detected spectrum (called space charge effect, SCE) [2].

To prevent the overlap of photoelectron spectra, we have developed a dedicated XUV beamline based on High-order Harmonic Generation [3] that delivers femtosecond pulses with the required photon energy (80 -100 eV). This beamline will be fully described during the conference.

Thanks to the complete experimental and theoretical investigations on SCE, we have been able to optimize the experimental parameters in order to perform Tr-PES pump/probe experiments on Copper samples where the SCE has been strongly reduced. It allowed us to separate the influence of lattice dynamics on the PES from the SCE, as illustrated Figure 1.

Figure 1 .

 1 Figure 1. Pump/probe measurements and their corresponding SCE simulations showing the Cu PES evolution. The difference in positive delays is attributed to the PES modification due to lattice dynamics. Inset: spectra normalized and superimposed to match the signal value of / . The signal is then measured at . .