Keywords:

Cellular Automata for the Observation of Complex Systems

In this thesis, we propose to study the observability of cellular automata (CA), i.e. how we can efficiently reconstruct the state of a CA from a limited number of measurements. To do so, we draw our inspiration from the notion of observability in classical control theory. This notion guarantees that the state of a system can be perfectly reconstructed from the measurements.

) and use it to define the notions of measurements and sensor networks for CA. Utilising these definitions we then develop the concepts of observability, reconstructibility, and adaptability in the context of cellular automata.

Subsequently, we define analytical criteria to verify these three notions for specific families of CA. We start with additive and affine CA for which we transpose the rank condition developed by Kalman and adapt it to provide similar conditions for reconstructibility and adaptability. Next, we focus on non-linear CA. We optimise observability and reconstructibility criteria for Boolean networks. We also propose a method for decentralising the observability analysis which may be applied to check observability and reconstructibility for very large CA.

We propose then another observation method with a totally different approach based on synchronisation. It avoids the computational complexity issues encountered using previous methods. In particular, in the case of small initial error, we propose an improved synchronisation method that drastically increases observation performance.

We conclude the thesis by illustrating the developed methods on three examples. We apply reconstructibility and synchronisation methods to a forest fire propagation model. We compare the observation performance of both methods. Then, we use reconstructibility and decentralised reconstructibility on a road traffic model. Finally, we use the observability of additive CA to reconstruct a sequence of numbers produced by a CA-based random number generator.

"Never gonna give you up, Never gonna let you down"1 are words that I have not heard, but that I have understood through the actions of all the people who have accompanied me during these three years. I would like to thank all the people who have contributed -directly or indirectly -to the accomplishment of my thesis work, materialised by the present document.

I would first like to thank my thesis supervisors, Samira El Yacoubi, Laurent Lefèvre and Clément Raïevsky, who have accompanied and advised me during these three years of thesis. Their complementarity on the scientific level offered me a space of great freedom while ensuring a rigorous work. Their availability, patience and involvement allowed me to work efficiently while answering my questions, calming my fears and helping me to discover the different aspects of the profession of academic researcher. I frankly couldn't have hoped for a better supervision.

I would like to thank Enrico Formenti and Gilles Roussel for agreeing to review this thesis. Their careful readings of this thesis and their different profiles provided complementary reports that brought new perspectives on this work. I would also like to thank Bastien Chopard and David Defour for accepting to be a member of the supervision committee which ensured the good progress of the thesis every year. I finally thank Amira Mouakher and Franco Bagnoli who joined the previous ones to complete my thesis jury.

I would like to thank the members of the IMAGES research team, at Espace Dev, who welcomed me during this thesis. I would like to thank in particular my colleagues, for their discussions -scientific, administrative and others -over coffee: Pius Nwachukwu, Maude Loireau, Marie Simon-El Jai, Abdelhaq El Jai and Yves Maurissen.

I would like to thank all the PhD students I have met and exchanged with during these three years. Whether it was through the Perpignan PhD students' association, through academic mobility or through online exchanges. I would like to thank in Le chapitre 2 présente les bases nécessaires à la compréhension des autres chapitres. Nous commençons par présenter la définition formelle aux automates cellulaires [START_REF] Yacoubi | A mathematical method for control problems on cellular automata models[END_REF]. À partir de celle-ci, nous présentons les différentes règles de transition que nous utiliserons dans les chapitres suivants. Parmi ces différentes règles, les plus utilisés dans le reste du manuscrit sont les automates cellulaires élémentaires de Wolfram et les automates cellulaires additifs et affines. Dans la seconde partie du chapitre, nous décrivons différentes notions liées à l'observation des automates cellulaires. Les notions d'observabilité et de reconstructibilité sont des notions déjà existantes que nous avons adaptées aux automates cellulaires. L'adaptabilité, au contraire, est une nouvelle notion facilitant le lien entre l'observabilité et la reconstructibilité.

xiii

Chapitre 3

Dans le chapitre 3, nous donnons des critères qui permettent de vérifier l'observabilité, la reconstructibilité et l'adaptabilité pour certaines familles d'automates cellulaires. Dans un premier temps, nous étendons le critère d'observabilité classique de Kalman [START_REF] Kalman | On the general theory of control systems[END_REF] aux automates cellulaires additifs et affines. Nous donnons aussi un critère de reconstructibilité et d'adaptabilité pour cette même famille. Ensuite, nous utilisons la représentation par graphe de transition d'état, ainsi que des résultats de l'observabilité et de la reconstructibilité des réseaux booléens [START_REF] Wang | Boolean modeling in systems biology: an overview of methodology and applications[END_REF], pour proposer un algorithme permettant de vérifier l'observabilité et la reconstructibilité des automates cellulaires non linéaires (non additifs). Finalement, nous présentons une méthode d'observation des automates cellulaires qui permet de définir un critère d'observabilité régionale et de décentralisation de l'observabilité pour les automates cellulaires non linéaires.

Chapitre 4

Dans le chapitre 4, nous présentons la synchronisation des automates cellulaires et nous l'étudions comme un estimateur d'état. Cette approche est sensiblement différente de celles présentées au troisième chapitre, car la bonne reconstruction de l'état par l'estimateur n'est pas caractérisée par l'observabilité ou la reconstructibilité, mais par une étude statistique. Dans un premier temps, nous présentons la synchronisation des automates cellulaires de Bagnoli [START_REF] Bagnoli | Synchronization and control of cellular automata[END_REF] et nous détaillons en quoi celle-ci est très proche de la formulation d'un estimateur d'état de la théorie du contrôle classique. Ensuite, nous caractérisons la propagation de l'erreur initiale dans les automates cellulaires élémentaires lorsque l'erreur initiale est faible. Finalement, à partir de cette caractérisation, nous pouvons présenter une nouvelle méthode de synchronisation lorsque l'erreur initiale est faible et nous comparons ses performances d'observation à la précédente.

Nomenclature

Introduction, Motivations and State of the Art

The modelling of natural phenomena is a crucial issue in understanding the world around us, for the prediction of future events or for the monitoring of current events. Especially as the world is undergoing major changes due to climate change. It is becoming urgent to develop such methods to cope with climate change issues. These approaches can be applied in a wide range of different domains and applications. This encourages the development of a theoretical formalisation in order to facilitate the deployment of this kind of tool in the future. The thesis goes in this direction and provides a few applied examples as well.

To give some context, let us look at the forest fires in the south of France. Between 2015 and 2019, over 8 700 forest fires were reported in the French Mediterranean area 1 , the most affected region of France. According to a recent inter-institutional study on the impact of climate change on wildfire hazards in France [START_REF] Chatry | Changement climatique et extension des zones sensibles aux feux de forêts. Rapport de la mission interministérielle CGAAER-CGEDD-IGA[END_REF], the risk of wildfires, currently concentrated in the Mediterranean area of France, would spread to the vast majority of France and particularly to the north of France by 2070. It is therefore necessary to provide the authorities with efficient methods to estimate the risk of fires and to monitor the progress of fires when they occur.

Forecasting and monitoring methods are not only useful for monitoring forest fires but can also be used to study other systems, e.g. to study the spread of epidemics [START_REF] Matt | Networks and epidemic models[END_REF], to predict desertification in sub-Saharan Africa [START_REF] Koné | Coupling cellular automata with medalus assessment for the desertification issue[END_REF], or to detect fake news in social media [START_REF] Zhou | Fake news early detection: A theory-driven model[END_REF]. The examples are numerous and that is why we wish to study these methods theoretically without being constrained to a single type of system or field of application.

To build such methods, two elements are needed: a good knowledge of the dynamics of the phenomena and information about it at a given time. From this we can predict, with an accuracy that depends on the two elements provided, how it will evolve. Information about the system is determined through measurements, which can be satellite imagery or data from sensors placed in the environment. The knowl-edge of the dynamics, called a model, can take different forms (cellular automata, partial differential equations, etc.). These notions of model and measurement, at the core of this thesis, will be developed with more detail in the next paragraphs.

This thesis proposes different methods to build useful tools for the monitoring of natural phenomena, and more generally complex systems. Hereafter, we start by an introduction to the different concepts discussed in this thesis. To begin with, we will focus on the notion of model and what it means. We will present different forms that a model can take and we will explain why we have chosen cellular automata for our study. Then, we will present the notions of measurements and observation of a system. The notion of observation, when studied through system theory, has a particular definition that we will present in detail. Then, finally, we will present the plan of this thesis which will put forward the methods of observation that we developed.

MODELLING OF COMPLEX SYSTEMS

System and Model

Before discussing the notions of modelling and system model, we need to introduce what a system is and what it is about.

What is a system?

A system is a set of components that interact with each other to form a meaningful group. Systems can represent physical, digital or even conceptual entities. As an example of a system, we could mention several systems with very different components: A car is a system where the components are the parts of the car ; The internet is a system where the components are servers, computers and communication channels ; A forest fire is a system where the components are the trees that compose the forest, the wind that helps the fire to spread, and even the firefighters that prevent the spread of the fire. There are as many systems as there are ways of looking at reality. Systems can be classified into large families that encompass similar behaviour. We will discuss only about two: complex systems and distributed parameter systems.

Complex systems represent systems with a very large number of components. They are often characterised by the emergence of phenomena that occur at the system level and cannot be explained at the component level solely. Among these systems, we find economic systems such as the stock market, ecological systems such as ant colonies or digital systems such as the internet.

Distributed parameter systems (DPS) represent systems whose components vary continuously according to different coordinates (often space and time). They are usually represented by partial differential equations (see hereafter). As an example of DPS, we could propose the propagation of a forest fire, as the forest and the wind depends on both time and position.

As stated in the title of this thesis, we will pay particular attention to complex systems and in particular to those who are also DPS. Once the system and its components have been identified, the system can be modelled. This is the first stage in studying or predicting the evolution of a system.

What is a model?

A system model, or more simply model, is a representation for a system. It can take different forms, either deterministic or probabilistic, continuous or discrete, linear or non-linear. In physics, the model is constructed from quantitative data expressed in formal terms. From the model one derives possible observations that are confronted with experimental results. The model itself may be expressed using mathematical equations, or by means of other descriptions that are more suited, for instance, for a computer implementation. From this, two types of models can be distinguished, knowledge-based models and data-based models. In a knowledge-based model, the model uses internal variables that represent a physical quantity, for example the temperature for a forest fire propagation model. On the opposite, in a data-based model, the variables are "hidden", the model describes the behaviour of the system without taking into account the internal states of the system. It is usually constructed from a large amount of data. Such models are very common in deep learning. And there are a large number of models that fall somewhere in between. For example, the FARSITE simulator describes the propagation of fire as elliptical, without taking into account the temperature of the fire. The physical variables are "hidden" but the global dynamics of the system are not.

When is a model considered valid?

A model is associated with a domain of validity which describes in which context and to what extent the model is valid. To show the interest of the domain of validity of a model, let us take as an example two different models of gravitation. The first is the universal law of gravitation described by Newton between 1665 and 1685 which explains that any two bodies exert a similar but opposite force which depends on the distance. The second is the law of general relativity presented by Einstein around 1915 which describes that gravity is no longer a force, but a curvature of space-time which depends on the mass. These two models describe the gravitational force but at different scales. To calculate the trajectory of a tennis ball both model will provide a solution but Einstein's model is too sophisticated for this situation. Similarly, Newton's model would not be as accurate for modelling gravity when the gravitational field is too intense, for example near a black hole, or to explain the apsidal precession of Mercury.

What is important to remember is that a model is defined in terms of a domain of validity and that there is no point in taking a model that is too complex to solve much less complex problems. As Einstein said2 , "Everything should be made as simple as possible, but no simpler.".

Different Methods to Build a Model

As we have seen, there are many different models, but there are also many different methods of representing these models. We are going to present several knowledgebased methods to build complex or DPS models. The difference between several major types of models lies in the way the spatial phenomena in the system are represented. Indeed, they can be either represented through a continuum or discrete variable. On the one hand, the continuous solution provides a way to represent the evolution continuously with respect to time and space. On the other hand, discrete variable model are easier to handle. In the next few sections, we present 4 different methods: partial differential equations, network-based models, cellular automata, and agentbased models. The first one is a continuous one whereas the others are discrete.

In the discrete approach, the dynamics are often described locally. The system is modelled as a set of subsystems that interact with each other and not as a single large entity as in the continuous approach. This type of method is simpler to implement because scientists often describe local interactions between subsystems more easily than a whole system. The downside is that the equation that describes the system globally is not straightforward to find based on the local interactions. This problem will be investigated in the thesis since the observation of systems (see section 1.2) requires the expression of the system global dynamics.

Partial Differential Equations

Partial Differential Equations (PDE) are a set of equations relating derivatives of physical variables with respect to space and time. They have been widely used by physicists for several centuries. Examples are the Navier-Stokes equation for modelling Newtonian fluids, the Maxwell's equations for modelling electromagnetic fields or the equations governing a reaction-diffusion system. PDE can also be used to model more specific systems: [START_REF] Richard | A mathematical model for predicting fire spread in wildland fuels volume 115[END_REF] uses PDE to model the propagation of fires ; [START_REF] Black | The pricing of options and corporate liabilities[END_REF] use PDE to describe the dynamics of the stock market.

However, the development of such PDE models often takes a long time and requires expert knowledge in the considered application field, but also a strong background in mathematics and numerics. Existence of solutions and numerical simulations are already very complex problems by their own, not to mention analysis of their dynamical properties. All those problems typically involve radical model simplifications. Even so, only numerical solutions are achievable. They typically require intensive computational efforts and numerical analysis expertise. To overcome this, we can use methods that directly implement space and time in a discrete manner.

Network-Based Models

Network-based models are characterised by the presence of a number of components (nodes) that are only connected to a certain part of the other components. The behaviour of these components is then defined locally from the interactions made with the other components of the network. This type of model is widely used to model systems that are already present as networks such as social networks or computer networks. It can also be used to model other types of systems such as epidemics where two people are connected on the network if there is a possibility that they will transmit the disease (e.g. through in-person interaction).

Boolean networks are a particular type of network-based model. The components are logical variables (usually Boolean). Boolean networks are particularly used in bioinformatics where they are used to model the interactions between genes in the DNA. We will discuss the properties of Boolean networks in section 3.3, as an introduction to the study of observability for non-linear cellular automata.

Agent-Based Models

Agent-based models represent models where system components are modelled by agents. Each agent is an entity that interacts with other agents, but unlike networkbased models, there is no constraint on how agents can interact. It is also possible to add a social aspect to the agents so that they function as an organisation, this is called a multi-agent system. This type of model is rather difficult to study at the system level because the interactions between the agents may not follow predetermined formal rules.

Cellular Automata

Cellular automata (CA) are a special case of network-based models. The components, called cells, are placed on a lattice, often uniform, and interact with nearby compo-nents only. This makes it easy to model systems with local spatial dynamics. For example, CA can be used to model the dynamics of fluids through the interaction of particles in the fluid [START_REF] Hardy | Time evolution of a two-dimensional model system. i. invariant states and time correlation functions[END_REF]. In addition, CA are also widely used in the modelling of a wide variety of systems, from the modelling of clotting processes [START_REF] Ouared | Lattice boltzmann simulations of blood flow: non-newtonian rheology and clotting processes[END_REF] to the modelling of desertification in sub-Saharan Africa [START_REF] Koné | Coupling cellular automata with medalus assessment for the desertification issue[END_REF]. [START_REF] Chopard | Cellular automata[END_REF] provides numerous tools on the modelling of physical systems through cellular automata.

Several CA, with different domains of validity, can be used to model the propagation of a forest fire. The simplest one we can think of is to represent the evolution of the fire by discrete states: tree, burning tree and burnt tree. The fire spreads from one cell to its neighbours. [START_REF] Karafyllidis | A model for predicting forest fire spreading using cellular automata[END_REF] propose a more complex model that uses the burnt biomass as a state, which can take into account different parameters such as wind or topography. CA are also used in more complex fire propagation simulators such as FlamMap [START_REF] Mark | An overview of flammap fire modeling capabilities[END_REF]. These simulators are used by firefighters to anticipate fire spread and act accordingly. This simulator simulates several variables such as fire, wind or humidity that interact together.

Another advantage of cellular automata is the ease of parallelisation. Indeed, the computation of the state of each cell depends only on the state of the neighbouring cells at the previous time. Therefore, it is very easy to parallelise the computation of each cell, as for agent-based models. When the neighbourhoods used by the CA are regular then it is possible to parallelise on GPU which increases even more the possibility of parallelisation and allows a gain of performance when it comes to the speed of calculation compared to the PDE.

Translated with www.DeepL.com/Translator (free version)

OBSERVATION OF COMPLEX SYSTEMS

Now that we understand the notion of system, we can make the observation of it.

But first what is observation? In this context, we define the observation as the action of gradually reconstructing the state of the system on the basis of measurements.

Measurements represent partial information on the system taken by sensors. There are two main types of reconstruction, one based on data and the other on model.

The first one uses a large number of measurements and process the data to extract the state of the system. Such methods are used for instance with Wireless Sensor Network or Big Data. The other method uses a smaller number of measurements but takes advantage of a model of the system to carry out the reconstruction. Such methods are used in control theory to build controllers which are widely used in different fields of engineering.

In this thesis, we will focus on the second method, more specifically on control theory approaches and how they can be applied to CA. In the next few paragraphs, we will present a short history of control theory, the main problems of studying DPS through control theory and the state of current research on control theory for CA.

Control Theory and Distributed Parameters System

Initially, control theory referred to the regulation of a physical process. In this sense, it has existed for several centuries (e.g. the centrifugal regulators of James Watt created in 1788). This thesis refers instead to the recent formalisation of control theory that emerged in the 1950s based on dynamical systems representation (state space or external). Among the works of this time, the best known are those of [START_REF] Kalman | On the general theory of control systems[END_REF] on linear systems with notably the definition of controllability and observability. Roughly speaking, controllability guarantees that there exists a regulator for this system and observability guarantees that the state of the system can be reconstructed correctly from measurements. It is the latter that we will study in this thesis. Since then, control theory has become widely known in a field of engineering known as control engineering.

Control theory can study linear or non-linear systems, continuous or discrete time, with one or more inputs. The study of DPS, however, remains largely open. The spatial dimension poses various problems related to infinite dimensional space and operators. Roughly speaking, this means studying a spatial continuum of timedependent variables. In addition to the computational difficulties of studying PDE, many results of classical control theory do not apply to DPS directly. For example, the notion of observability is separated into two different notions: an exact observability and an approximate observability. Exact observability is similar to usual observability, whereas approximate observability guarantees that the state of the system can be reconstructed only approximately [START_REF] Glowinski | Exact and approximate controllability for distributed parameter systems[END_REF]. The two notions coincide in the case of classical systems.

In some cases, the observability of the system can only be assured for a part of the system. [START_REF] El | Regional observability and sensor structures[END_REF] present a regional study of observability and controllability that provides methods to study only a small region of the system. Controllability and observability therefore have particular definitions that relate to the region under study. Even if the verification is more complicated, it still ensures partial observability where it would not otherwise be possible.

Control Theory of Cellular Automata

There is little work addressing the control theory of CA. [START_REF] Yacoubi | A mathematical method for control problems on cellular automata models[END_REF] proposes a definition of cellular automata that encompasses the notions of actuators and control.

The regional controllability is presented and illustrated in the context of an additive CA. Regional controllability has also been studied by Dridi et al. in different ways. In [START_REF] Dridi | A graph theory approach for regional controllability of boolean cellular automata[END_REF], it is evaluated using graph theory and Hamiltonian paths, in [START_REF] Dridi | Markov chains approach for regional controllability of deterministic cellular automata, via boundary actions[END_REF] it is checked using a Markov chain. The studies of these two authors focus on regional controllability where, contrary to the cases of classical theory, the duality between controllability and observability is not trivial. In [START_REF] Urıas | Synchronization of cellular automaton pairs[END_REF], the observability of an additive CA is studied in a hidden way. The authors place sensors so as to ensure that a matrix is invertible, which is a hidden application of the Kalman condition.

Alternatively, if we constrain the definition of CA to bounded and finite state CA then it can be studied as a Boolean network. The control theory of Boolean networks has been widely studied since the early 2000s with contributions from [START_REF] Cheng | Semi-tensor product of matrices and its applications to dynamic systems[END_REF] on the semi-tensor product and [START_REF] Laschov | Observability of boolean networks: A graph-theoretic approach[END_REF] on the observability graph.

Nonetheless, CA exhibit certain advantages compared to PDE. Indeed, they represent the spatial dimension in a discrete way. Consequently, for a finite space, the number of variables is finite. This leads to the use of the results of the classical finite dimensional control theory in the case of a DPS. In particular, it is possible to use Kalman rank condition on controllability and observability.

CONTRIBUTION AND CONTENT OF THE THESIS

In this thesis, we will focus on the observation of complex systems and in particular DPS. PDE are very powerful tools for the study of such systems, but their studies can be very difficult. Among discrete systems, CA seem to be the most suitable models for modelling DPS, due to the strong spatial component. CA are models where the time and space are discrete. We will use them as a model for DPS. Therefore, the systems modelled by CA are not strictly DPS but will have the same behaviour regarding their validity domain. Although CA are less precise than PDE, their domain of validity will be sufficient for the purpose of the thesis, which is the observation of spatially distributed physical systems. This thesis contributes to the observation of complex systems in three ways:

• firstly with a formal definition of observability, reconstructibility and adaptability, three notions related to the reconstruction of the state of a system from measurements. Observability and reconstructibility are two notions that we have applied to cellular automata while adaptability is a new notion presented in this thesis that provides a way to verify that the sensors are well suited for the observation of the system.

• secondly, by providing analytical criteria to verify the previous notions. For additive and affine CA, the Kalman condition for observability is adapted for CA and similar criteria are given for reconstructibility and adaptability. For nonlinear CA, the criteria are derived from the observation of Boolean networks. They are adapted to take advantage of the benefits of CA in order to reduce the algorithmic complexity. A decentralised observability and reconstructibility verification method is given to further reduce the complexity in the case of CA with a large number of cells.

• thirdly, by studying the synchronisation of CA as a state estimator. This method is not derived from control theory and does not depend on observability or reconstructibility. Its efficiency is statistically evaluated through a large number of simulations. An efficient synchronisation method is given for the observation of a system where the initial error is small.

The manuscript is organised in 6 chapters that present the contributions, examples and conclusions on future work.

Chapter 2 serves as a definition for CA and notions related to observation. It presents in detail the definition of CA by El Yacoubi as well as different properties of CA that will be used in the sequel. The notions of observability, reconstructibility and adaptability are presented and serve as a basis for the control theory of CA.

Chapter 3 presents analytical criteria to verify the three notions defined previously. First, criteria are given for additive and affine CA by generalising the Kalman rank condition. Then, criteria are given for non-linear CA which are studied as Boolean networks. Finally, in the last part of this chapter, methods are presented to handle the algorithmic complexity raised by the criteria through the decentralisation of the verification for observability.

Chapter 4 presents an alternative observation method based on CA synchronisation. We present synchronisation as a state estimator for CA observation. We then present a more efficient method for CA observation when the initial error is very small.

Chapter 5 presents three examples which aim to illustrate the methods presented in this thesis on simple examples. The first example deals with a forest fire propagation model that we use to compare the performance of reconstructibility against synchronisation. Secondly, we present a road traffic model for which we try to apply the proposed observation decentralisation approach. We end with an example on the reconstruction of random numbers generated by a CA random number generator, which allows us to describe the use of the methods on additive or affine CA.

Chapter 6 concludes this thesis by providing an overview of the prospects and outlining future work that might follow on from the research carried out in this thesis.

CHAPTER 2

Cellular Automata as a Modelling Tool RÉSUMÉ L'objectif de ce chapitre est de présenter les bases nécessaires à la compréhension des autres chapitres. Dans ce but, nous présenterons les automates cellulaires comme un outil de modélisation des systèmes complexes, mais aussi les notions d'observabilité et de reconstructibilité, liées à l'observation de ceux-ci. Dans une première partie, nous définirons les automates cellulaires ainsi que les différentes règles de transition que nous utiliserons dans la suite du manuscrit. Dans la seconde partie, nous présenterons les notions de capteurs, d'observabilité, de reconstructibilité et d'adaptabilité, liées

INTRODUCTION

The observation of a complex system may be realised through the use of a mathematical description of the process to be observed. This description is a partial representation of the reality written with mathematical equations and is called a mathematical model or a system model. To describe a system (whether complex or not) with such a mathematical model, it is necessary to have both a working knowledge of its parts and a precise idea of the applications for which the model will be used. The model is thus intimately related both to the system and its application.

For complex systems (i.e. with a large number of subsystems), the use of PDE becomes too complicated. The different time and spatial scales, as well as the different variables of the subsystems, make it extremely difficult to establish equations that describe the whole system. In this context, cellular automata (CA) appear as a good alternative because only the local dynamics (i.e. relating the variables characterising neighbour subsystems) are used as equations. The global dynamics is obtained as the superposition of all the local dynamics.

The objective of this chapter is to present CA as a tool for modelling complex systems and to give all the theoretical tools necessary to understand this work. We start with a short history of CA followed by a mathematical formalisation of these. Then, we present the elements that make a CA a good tool for modelling complex systems and finally, we describe the tools necessary to observe complex systems modelled by CA.

GENERALITIES ON CELLULAR AUTOMATA

Brief History of Cellular Automata

The history of CA begins in the 1940s with the collaboration of John Von Neumann and Stanislaw Ulam, two mathematicians from the National Laboratory of Los Alamos in New Mexico (USA). John Von Neumann was working on self-replicating systems and Stanislaw Ulam on crystal growth using a grid. This collaboration led to the creation of the first cellular automaton: the "universal copier and constructor", a selfreplicating system that uses a two-dimensional grid.

CA were not extensively studied in the 40s and 50s due to the lack of computing power provided by computers at this period. It is only from the end of the 60s that CA start to be widespread in the mathematical community, notably thanks to the works of Gustav A. Hedlund, who studied CA as a dynamic system in its own right.

It is in the 70s and 80s that the foundations of today's cellular automata are laid with notably the works of: John Horton Conway on the game of life [START_REF] Conway | The game of life[END_REF]; Stephen Wolfram on elementary cellular automata [START_REF] Wolfram | Statistical mechanics of cellular automata[END_REF]; and Hardy, Pomeau, and De Pazzis on the HPP model [START_REF] Hardy | Time evolution of a two-dimensional model system. i. invariant states and time correlation functions[END_REF]. John Horton Conway proposed the game of life, a CA defined by extremely simple rules but able to show complex global behaviour (notably proven to be a universal Turing Machine). Hardy, Pomeau, and De Pazzis developed the HPP model, a CA capable of simply modelling the behaviour of fluids through the interaction of its particles, which would later become lattice gas automata (Wolf-Gladrow, 2004, Chap 3) or lattice Boltzmann methods (Wolf-Gladrow, 2004, Chap 5). Stephen Wolfram published in the 80s a series of systematic studies on elementary CA (the simplest ones) showing the existence of different types of behaviour and allowing classifying elementary cellular automata according to their properties.

Finally, it is from the beginning of the 90s that cellular automata start to be widespread as a tool for modelling physical [START_REF] Chopard | Cellular automata[END_REF] or biological systems.

Definition of Cellular Automata

There are many definitions of CA, both formal and informal, which vary from one application to another and from one domain to another. Among all these definitions, there are two central points. The first is the "cellular" aspect of the CA, whereby the space is divided into elementary parts called cells and each of these has a state that describes its nature. The second point concerns the evolution of the state of the cells over time. The evolution of a cell's state depends both on the state of this cell and on the states of neighbouring cells. This rough definition allows us to consider the use of CA for applications involving a large number of entities that interact locally (complex systems), in fluid mechanics (local interaction of the particles making up the flow of the fluid) or in the representation of spatially distributed transport phenomena (such as forest fire spread), just to cite a few examples.

Our objective is to formally define cellular automata as a tool for the observation of complex systems. We will therefore use a definition of CA adapted to the observation problem, namely the one proposed by [START_REF] Yacoubi | A mathematical method for control problems on cellular automata models[END_REF]. The author proposes therein a definition of bounded cellular automata suitable for control. In addition to this definition, the corresponding state equation, as well as the notions of actuators and regional controllability, are also presented. We will detail these notions in section 2.3.1, when considering the duality between observation and control problems. For the time being, we restrict ourselves to the definition 2.1 of bounded cellular automata. Definition 2.1 (Cellular Automata). A bounded cellular automaton is defined by a quadruple A = (L, S, N, ) where:

• L is a -dimensional finite lattice of cells (a generic cell will be denoted , in the sequel) which are spatially arranged according to their shape. We denote by ∈ N the number of cells in L.

• S denotes a finite set of admissible state values for the cells. We usually represent a set of -states by the finite commutative ring S = {0, 1, . . . , -1} which uses modular arithmetic. S may also be written as S = Z/ Z.

• 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 ( ) = { 1 , 2 , . . . , } (2.1)
where the cells , for ∈ 1, , are linked to the cell by an influence relation.

In most of the case, the cell is in its neighbourhood. In the case of bounded cellular automata, it is necessary to take into account the lattice boundary conditions (see Figure 2.2) in the construction of the neighbourhoods.

• is a transition function which determines the cell's state at time + 1 given the state of the neighbouring cells at time . It is defined by:

: S → S (N ( )) ↦ → +1 ( ) = ( (N ( ))) (2.2)
where ( ) represents the state of the cell at time and (N ( )) = { ( )| ∈ N ( )} is the state of the cells in the neighbourhood at time t.

This definition, although very general, largely limits the possible applications with this kind of CA. The bounded lattice removes the universal Turing machine property and the finite number of states hinders the representation of continuous state CA such as the forest fire spread model of Karafyllidis and Thanailakis or the Lattice Boltzmann methods, both discussed in the introduction.

In the following subsections, we clarify the different components presented in definition 2.1. We present the most common lattices, neighbourhoods and boundary conditions that are used in CA.

Global Transition Function

In some cases, in particular to solve the observation problem (see section 2.3.3), we need to model the local transition function as a so-called global transition function. It applies simultaneously to all the cells of the CA and not only to the neighbouring cells. It is used for example to define the state transition diagram or the state representation, two very important notions that we will use in chapter 3.

Therefore we start by defining the state of all cells in the CA, ∈ S L , called the configuration at time . It is defined by the application :

: L → S ↦ → ( ) (2.3)
The transition from one configuration to another is determined by the global transition function defined by :

: S L → S L ↦ → ( ) = +1 (2.4)
The transition function describes the local evolution (i.e. at the cell level) of the CA, whereas the global transition function describes the global evolution (i.e. at the configuration level). However, the transformation from one transition function into the other is not a simple problem. One of the first issues in solving the observation problem will be to obtain the global transition function because most CA are defined through the local transition function .

Due to the finiteness of the state space S and the lattice L of the CA, we provide the definition 2.2 which allows us to represent the configuration by a number in base . For example, 230012 |4 represents the configuration such that ( 1 ) = 2,

( 2 ) = 3 and so on. This configuration corresponds to the number 2822 in base 10.

Definition 2.2 (Numerical Notation of Configuration)

. By arranging the cells of the lattice in any given arbitrary order, we can represent the configuration by an -digit number in base , denoted by | . It also has a unique equivalent in base 10.

Lattice of Cells L

In the vast majority of cases, the topology of the lattice is regular, i.e. it consists of a single shape and size of cell to cover the space. In the one-dimensional case, the cells are points arranged in a line, but it is usual to represent them as a line of square cells.

In the two-dimensional case, several regular lattices exist, the most commonly used being the square, triangular or hexagonal cell lattices. The use of one lattice or another can change the possible dynamics of the modelled system. For example, in the case of the HPP Model (Wolf-Gladrow, 2004, Chap. 3/sec. 1), the lattice of square cells allows the particles to spread in 4 directions, whereas in the FHP Model (Wolf-Gladrow, 2004, Chap 3/sec. 2), 6 directions can be available by using a lattice of triangular cells.

Set Space S

In definition 2.1, the state of the cell S is presented as a finite set of natural integer S = {0, 1, . . . , -1}. In chapter 3, when we discuss the observability of additive and affine CA, we will need to perform some mathematical operations on these states (in particular the inverse of the modular multiplication). Therefore, it will be necessary to consider S as a finite field (or Galois field), in this case a finite commutative ring with a prime number of states . However, in some specific cases discussed in the introduction, the state of the cells is not an integer but a word (tree or burning tree as in the trivial example of the fire spread model), a colour (black or white as in the game of life) or any other discrete value. In those particular cases where the state of the cells is not represented by integers, values of the state space S are simply arbitrary values which correspond to the states of the cells. For example, in Conway's Game of Life [START_REF] Conway | The game of life[END_REF], colours white and black can be respectively represented by the integer 0 and 1. definition 2.1 can still represent CA that do not have integer states (as described in the definition).

Neighbourhood N

Most of the work on CA use uniform neighbourhood, that is the neighbourhoods are identical for all the cells in the lattice and defined through a distance to the central cell. If some cells in some particular neighbourhood have no influence on the future state of the considered cell, then the transition function will be chosen appropriately, while the neighbourhood definition itself remains the same for all cells. Therefore, we can define the neighbourhood formally by the following relation:

N : L → L ↦ → N ( ) = { ∈ L| - ≤ } (2.5)
where represents the -norm. Among the possible norms, the most used are the taxicab norm ( = 1) or the infinity norm ( = ∞).

These two norms allow different cells to be included in the neighbourhoods, norm 1 includes only cells that are adjacent by a side whereas norm ∞ includes cells adjacent by a side but also by a corner. This difference is visible, on Figure 2.1, in the case of a two-dimensional mesh with square cells.

In the one-dimensional case, these two norms are equivalent because there are no corner-adjacent cells. In the case of a two-dimensional lattice with square cells, these two norms correspond to the Von Neumann ( = 1) and Moore ( = ∞) neighbourhoods. Figure 2.1 shows different neighbourhoods with different distances for 2D lattices with square cells. For a hexagonal cell lattice, these two neighbourhoods are equivalent (as for a 1D square cell lattice) and we use the term uniform neighbourhood.

(a) = 1; = 1 (b) = ∞; = 1 (c) = 1; = 2 (d) = ∞; = 2

Boundary Conditions of the Lattice

In the case of a bounded CA (such as in definition 2.1) the lattice is finite and the neighbourhood of the cells on the border depends on cells that do not exist in the lattice. We must therefore consider the value of the cells directly outside the lattice. These are called boundary cells. In addition, since some physical systems admit natural boundaries, it is natural to be able to define these boundaries in their CA models. This is known as a boundary condition. Three types of boundary conditions are usually considered: periodic, reflexive, and fixed (see Figure 2.2).

• Periodic boundary conditions allow the system to be looped back on itself, whereby the state of the boundaries on one side corresponds to the state of the cells on the other side of the lattice. In the two-dimensional case, a lattice with periodic boundaries is in fact the surface of a torus.

• Reflexive boundary conditions correspond to the situation where the cells located on the boundary of the lattice have themselves as neighbours.

• Fixed boundary conditions correspond to boundary cells that have a value that is determined by the CA designer. This value can vary from one cell to another and can also vary as a function of time (known as a boundary trajectory). In some applications it is also referred to as a null boundary condition, which corresponds to a fixed boundary condition of 0. In many cases it has a special meaning, for instance, the "void" or "quiescent" state. In some particular cases, especially when we address the decentralisation of observability (see section 3.4 on page 71), we are only interested in one region of the CA. To study the observability of this region, we model it by a separate CA, while the rest of the outer cells are only considered through the boundary conditions. They do not respect any of the three types of conditions defined previously as they are simply the state of cells of the larger CA. These are called here unknown boundary conditions.

Families of Cellular Automata

To carry out a systematic study, which applies to all CA, proves to be an impossible task. Therefore, the properties of CA are often studied for some specific families which are obtained by introducing constraints on the definition. One of the earliest and most influential studies of this kind was conducted on elementary cellular automata (CA with one-dimensional lattices, Boolean state space, and neighbourhood of radius 1) by [START_REF] Wolfram | Statistical mechanics of cellular automata[END_REF]. More recently, several studies by Chaudhuri et al. have been published in a book [START_REF] Pal Chaudhuri | Additive cellular automata: theory and applications volume 43[END_REF] gathering results on additive cellular automata (CA with linear transition function). Many other studies have been conducted on other families of CA such as totalistic CA by [START_REF] Wolfram | Universality and complexity in cellular automata[END_REF] or two-dimensional CA by [START_REF] Norman | Two-dimensional cellular automata[END_REF].

In this section we will introduce many families, but we shall concentrate on the one we will consider later. We will define these families through the definition 2.1, which will allow us to use them in the following chapters of this thesis.

Wolfram's Elementary Rules

The elementary rules of Wolfram have been defined in [START_REF] Wolfram | Statistical mechanics of cellular automata[END_REF] with the purpose of performing a systematic study of the behaviour of CA. These rules are considered elementary because they are the simplest non-trivial CA: the lattice is onedimensional, the state space has 2 state (Boolean state space) and the neighbourhood of distance 1 (it includes only the two directly adjacent cells and the cell itself). Based on the definition 2.1, Wolfram's elementary cellular automata (ECA) are defined by: • L = 0; -1 is a one-dimensional lattice of cells.

• S = {0, 1} is a Boolean state space. In a Boolean state space, we have the possibility to use Boolean or modular arithmetic. In this case, we will use three operators (logical AND "•", logical OR "+" and logical NOT " ") for the Boolean arithmetic and two operators (product modulo 2 "•" and addition modulo 2 "⊕") for the modular arithmetic. The logical AND and the multiplication modulo 2 are equivalent as well as the addition modulo 2 "⊕" and the logical XOR.

• N : ↦ → { -1 , , +1 } is the neighbourhood of distance 1 which includes the central cell and its two direct adjacent cells. By default, we use the periodic boundary conditions but any other boundary conditions can be used.

No specific constraint has been placed on the transition function as the purpose of Wolfram was to study the behaviour of every possible transition function. In a similar way to a ternary logical operator, the transition function is defined by a truth table that maps the state, at time , of the 3 neighbouring cells to the state, at time + 1, of the central cell (see Table 2.1). Since each of the three cells in the neighbourhood have a Boolean state, there are 2 3 = 8 entries in the truth table and they are associated with a digit that represents the state of the central cell at the next time step. The transition function of the ECA is therefore described by these 8 digits. Each of the possible transition functions can be represented by an 8-bit number called Wolfram's elementary rule number. These numbers are arranged in descending order of the integer number whose development in base 2 is obtained from the binary values of the 3 neighbouring cells (i.e. the neighbourhood value 101 corresponds to the integer value 5), as shown in Table 2.1. An example of the evolution of this rule is given in Figure 2.3 for 15 cells and periodic boundaries. The notation "rule 90", which will be abbreviated to R90, gives all the information about the behaviour of the transition function but nothing about the size of the lattice or the boundary conditions. Therefore, we define a more detailed notation RX-N-B 1 0 1 0 1 1 1 0 0 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0 1 1 F . . Example of configuration evolution of the ECA of Table . . The cells on the ends are the boundary condition cells (here periodic condition) used in the neighbourhood calculation.

which includes not only the rule number X, but also the number of cells N as well as the nature of the boundary conditions B as described in Although initially defined by a truth table, the transition functions of ECA can also be written in algebraic form using either modular arithmetic (see eq. (2.6)) or Boolean arithmetic (see eq. (2.7)). These algebraic forms, although equivalent, are used in different scenarios depending on their ease of use. For example, if one is interested in Boolean derivatives of transition functions then modular arithmetic is preferred and if one is attempting to emulate CA with logic gates then Boolean arithmetic is preferred.

Example 2.1

The following are the two algebraic forms of R90 defined by the truth table in Table 2.1. The first uses modular arithmetic and the second Boolean arithmetic.

+1 ( ) ↦ → ( -1 ) ⊕ ( +1 ) (2.6) +1 ( ) ↦ → ( ( -1 ) • ( +1 )) + ( ( -1 ) • ( +1 )) (2.7)
Although these CA are elementary, they are not without interest for the modelling of complex systems. In mathematics for instance, ECA can be used for the generation of fractal figures like the Sierpiński triangle with R126 on Figure 2.4 (other rules like R60, R90, R150 generate variants of this figure). R110 (with an infinite lattice) has the property of being Turing Complete [START_REF] Cook | Universality in elementary cellular automata[END_REF], i.e. R110 can simulate Turing machines where the writing of the algorithm is carried out in the choice of the initial configuration. Physical systems can also be modelled using these ECA: R30 can generate the figures naturally present on the shells of the Conus Textile1 (see

Additive Cellular Automata

Additive cellular automata (ACA) have first been used to study the algebraic properties of CA [START_REF] Martin | Algebraic properties of cellular automata[END_REF]. In this paper, Martin et al. use ACA to study the state transition diagram and the length of the cycle in the graph, we discuss that point on section 2.2.4. They have since been used in different ways, such as a random number generator [START_REF] Tomassini | On the generation of highquality random numbers by two-dimensional cellular automata[END_REF], or a hash function (Chaudhuri et al., 1997, Chap. 8).

Many of the possible applications of ACA have been compiled in the book "Additive cellular automata: theory and applications" by Chaudhuri, Chowdhury, Nandi, and Chattopadhyay. The element that bounds together all these CA is the nature of their transition function. Indeed, the transition function is defined as a weighted sum of the states of the neighbouring cells. Using definition 2.1, the transition function can then be defined as:

: S → S (N ( )) ↦ → +1 ( ) = =1 • ( ( ) ) (2.8)
where ( ) is the th cell in the neighbourhood of the cell as shown in Figure 2.7, is the weight applied to the state of the cell ( ) , and is the number of cells in the neighbourhood.

Note that the does not represent the cell number but the position of the cell in the neighbourhood. Indeed, the weights of the transition function are defined in relation to the position of the cell within the neighbourhood, as shown in Figure 2.7, and not in relation to a particular cell in the CA.

F

. . Example of the weights applied for a D additive cellular automaton with a Moore neighbourhood and a state space with (at least) 6 states. The number in the upper left corner of each cell represents the number of that cell in the neighbourhood while the central number represents the weight applied in the sum.

Remark 2.1. Two-dimensional ACA (or one-dimensional ACA represented in the form of a 2D ACA of size 1 × ) can be computed through a 2D convolution using the neighbourhood with the weights (as in Figure 2.7) as the convolution filter. The CA must still be augmented by representing the boundary conditions as cells, so that they are taken into account in the convolution.

Since the transition function is linear over the state of all cells in the neighbourhood, is therefore a linear form 2 over the commutative ring S. Using the properties of linear form, the local transition equation can be written with a matrix product between the row vector of the sum weights and a column vector composed of the states of the neighbourhood cells. 1) ) ( ( 2) ) . . .

+1 ( ) = 1 2 . . . •          ( (
( ( ) )         
(2.9)

By slightly adapting this function, we are able to describe the evolution of the state of a cell as a function of the configuration, i.e. the state of all the cells of the CA and not only those of the neighbourhood. To do this, we apply the weight 0 on the cells that are not in the neighbourhood. Moreover, we note ∈ S the vector representation of the configuration ∈ S L . For consistency with definition 2.2 on the numerical notation of configurations, the same order of cells must be taken for the arrangement of and | . Therefore, we obtain the equation (2.10) which describes the evolution of the cell as a function of the configuration .

+1 ( ) = • = ,1 ,1 . . . ,1 •          ( 1 ) ( 2 ) . . . ( )          (2.10)
where , is the weight applied to the state of cell in the calculation of the state of . If the cell is in the neighbourhood ( ∈ N ( )) then the value of , is the weight associated to its position in the neighbourhood and it is 0 otherwise. Having formulated the evolution of the state of a cell according to the configuration , we can build the global transition function which uses the matrix which is composed of the rows , ∀ ∈ 1; .

: S → S ↦ → +1 = • =          1,1 1,2 . . . 1, 2,1 2,2 . . . 2, . . . . . . . . . . . . ,1 ,2 . . . ,          •          ( 1 ) ( 2 ) . . . ( )          (2.11)
This matrix expression of the global transition function will allow us to apply the results from linear system theory to CA, as discussed in chapter 3.

Affine Cellular Automata

Additive cellular automata represent only a small fraction of the possible CA. For example, only 8 of the 256 ECA are additive (R0, R60, R90, R102, R150, R170, R204, R240) knowing that R0 and R204 are respectively the null and identity CA. Some of Wolfram's ECA are linear with respect to the Boolean negation of a cell. This is notably the case of R195 which is defined by +1 ( ) = ( -1 ) ⊕ ( ). In Boolean arithmetic, the NOT operation ( ) is equivalent to the XOR operation (or addition modulo 2) with 1, so the negation operation is represented by the addition of the constant 1. Therefore, in order to include these CA, and more generally every ACA with constants, we can adapt the definition by adding a constant vector ∈ S in the transition function (2.11) which then reads:

: S → S ↦ → +1 = • + (2.12)
We refer to these CA as affine cellular automata (or additive with a constant).

In the following, we will use the term ACA to designate both affine and additive cellular automata. Indeed, the results of chapter 3 apply to affine CA and thus also to the particular case of affine CA with a null constant, additive CA. We could simply use the term affine CA, but we wish to use both terms as additive CA is widely used within the CA community whereas the term affine (and linear to refer to affine with null constant) is more used in the system theory community.

Hybrid Cellular Automata

Some cellular automata, notably the [START_REF] Tomassini | On the generation of highquality random numbers by two-dimensional cellular automata[END_REF] random number generator studied in chapter 5, have a local transition function that varies from one cell to another. Such cellular automata are known as hybrid CA. We can adapt definition 2.1 by adding a dependency on the cell position to the transition function. Then will be defined as:

: S → S (N ( )) ↦ → +1 ( ) = ( (N ( ))) (2.13)
In the case of hybrid ECA, the notation 90, 160, 253, 126 is used [START_REF] Choudhury | Investigation of the global dynamics of cellular automata using boolean derivatives[END_REF] to describe the rule of each cell of the CA. In this case, the first cell follows R90, the second R160 and so on. Using the notation of Table 2.2, we can replace the number of the rule X and the number of cells N by the notation •, •, • . Therefore, if the hybrid ECA 90, 160, 253, 126 has periodic boundaries, we can write R 90,160,253,126 -PB.

For additive and ACA, the transition function, defined by (2.8) is described by the weights and the constant . Thus, the weights will depend on both the position of the cell in the neighbourhood and on the position of the cell on the lattice. Therefore the transition function is defined by :

: S → S (N ( )) ↦ → +1 ( ) = =1 , • ( ( ) ) + (2.14)

Probabilistic Cellular Automata

In some cases it is necessary to use probabilities when modelling a physical system. For example, probabilities are used to model a fire outbreak in a forest fire spread model or to reproduce an accident in a road traffic model. We must then transform the transition function of the CA into a random process. Therefore, probabilistic CA (PCA) may be defined in many different ways. We will use the formal definition from [START_REF] Mairesse | Around probabilistic cellular automata[END_REF].

In the probabilistic case, the local transition function does not allow computing the deterministic value for the state of the cells at the next time, but instead the probability distribution of a random variable with values in S. We will denote M (S), the set of variables with random value in S. Consequently, the global transition function does not provide a particular configuration, but instead a random variable with value in M (S L ). It will be defined as:

: M (S L ) → M (S L )
The vast majority of the definitions and results given in the rest of this thesis do not apply to PCA. For example, for a given configuration, there are several possible subsequent configurations, which makes many results, such as observability and reconstructibility (see section 2.3.3), irrelevant. The different observability and reconstructibility criteria given in chapters 3 and 4 will therefore not apply to PCA. On the other hand, other definitions and results may be easily adapted to PCA, like those on the state transition graph (see section 2.2.4 on State Transition Diagram and Attractor) which can be considered, in the probabilistic case, as the graph representation of a Markov process with a well-defined corresponding Markov matrix (once the transition probabilities have been defined). Furthermore, PCA are discussed in section 3.4 where they are used as a tool for observing deterministic CA.

Properties of Cellular Automata

Some properties are common to many (if not all) CA such as reversibility, state transition diagrams and complexity classes are directly related to the observability of CA. These will be used throughout this work and are defined in this section.

State Transition Diagram and Attractor

In the case of the CA definition 2.1 , the number of cells is finite as is the number of states for a cell. In addition, since the configuration is the application that associates a cell with its state, the number of configurations is also finite. Configurations are ordered arrangements of cells with values from the set (with states), so a total of possible configurations. Moreover, with the finiteness of the space of configurations S L , it is possible to represent the global transition function as a map which connects one configuration to another (which may be itself). By representing this lookup table as a binary relation (this representation is detailed in section 3.3 on page 54), we can define a graph (see Figure 2.8) from the adjacency matrix. This graph is called the State Transition Diagram and was first presented for CA by [START_REF] Martin | Algebraic properties of cellular automata[END_REF]. In addition, in their paper, Martin et al. use this diagram to illustrate the existence of attractor cycles. After a certain number of iterations and whatever the initial configuration, the state of the CA is in a cycle. The number and size of the cycle depend on every parameter of the CA. The state transition diagram represents the transition function as a graph and therefore make using graph theory results on CA possible. Using the numerical notation of the configurations (see definition 2.2), it is possible to number each node of the state transition diagram and thus define an adjacency matrix and a state vector that represents the configurations. For example, the configuration 0000010 of ECA has 2 for decimal value and is represented by the vector = 0 0 1 0 . . . 0 .

The first element of corresponds to the configuration with the value 0, the second to the configuration 1, and so on.

In this work, the notion of attractors and cycles was not explored but could have been used as a criterion of observability or reconstructibility as it was done by Laschov et al. (2013) (more details in 3.3.1). Hamiltonian circuits were used as a criterion for controllability of CA by [START_REF] Dridi | A graph theory approach for regional controllability of boolean cellular automata[END_REF] and the transmission, through duality, of such results to observability remains an open question, and not necessarily a trivial one.

Classes of Cellular Automata

In 1984, Wolfram proposed a classification of CA into four different classes. Initially studied with totalistic CA (CA whose evolution is described by the sum of the states of the cells of the neighbourhood as in the game of life), Wolfram extends these classes to every CA. They are defined according to the behaviour of the CA, for the vast majority of initial configurations, after a certain number of iterations. These classes are defined by :

• Class 1: Initial configurations evolve into a stable, homogeneous, and unique configuration for all cells. R32 shown in Figure 2.9a is an example of a class 1 ECA.

• Class 2: Initial configurations evolve into a stable configuration or an oscillating pattern (which is neither homogeneous nor unique). This class serves as a "filter" for the randomness of the initial configuration whereby only a few structures remain, the others being filtered out. R172 shown in Figure 2.9b is an example of a class 2 ECA.

• Class 3: Initial configurations evolve into a chaotic or pseudo-random (ergodic) pattern: no stable or repetitive state is reached. Wolfram defines a criterion of spatial ( ) and temporal ( ) chaoticities that quantify the chaoticity of the CA. Wolfram also proves that the injectivity of (reversibility) is a sufficient (but not necessarily) condition for maximal chaoticity ( ) = 1. R30 shown in Figure 2.9c is an example of a class 3 ECA.

• Class 4: Initial configurations evolve into different structures, which may be similar to other classes, interacting in complex ways. Wolfram conjectured that some of the rules would be Turing Complete (have the ability to simulate any Turing machine) which was proven for the rule R110 [START_REF] Cook | Universality in elementary cellular automata[END_REF]

Reversibility of Cellular Automata

Reversibility is a property of cellular automata that describes the possibility of finding the previous configuration -1 from the current configuration . This property must apply for all configurations of the CA. Reversibility is identical to the injectivity of the global transition function which ensures, for each configuration, the uniqueness of its antecedent. Some configurations have no predecessors, they exist only as initial configurations. These configurations are called gardens of Eden and are related to the surjection of the transition function . [START_REF] Edward | The converse of moore's garden-of-eden theorem[END_REF] and [START_REF] Edward | The converse of moore's garden-of-eden theorem[END_REF] define the Garden of Eden's theorem which binds the injection and surjection of CA, that is the non-existence of the Garden of Eden to the notion of reversibility.

Reversiblity is notably used for applications such as random number generation, hash tables, etc. In the case of Cellular Automata Random Number Generator (CA RNG) reversibility is used with a maximum cycle size to ensure equiprobability of the configurations (the random numbers) of the CA. An example of CA RNG is described in more detail in the chapter 5: Application to Monitoring of Complex Systems (see section 5.4 on page 129) where the notion of observability is used to retrieve information about the random number generator flow.

OBSERVABILITY AND RECONSTRUCTIBILITY OF CELLULAR AUTOMATA

The objective of the observation of a CA is to determine its internal state (i.e. its configuration ) using only partial measurements made on it. For this purpose, we will use a state estimator (or state observer). This is a system that has its own state (known to the user) and which we seek to converge to the actual state of the system. The first step is to choose the approach for estimating the state, but also to ensure that it works well for all (or for a large part of) the possible scenarios.

In classical control theory, it is possible to characterise whether or not there is a state estimator to reconstruct the state of the system given the dynamics of the system and the dynamics of the measurements. This characterisation, called observability, is given by Kalman and can be easily evaluated for linear systems. For non-linear systems, the verification is more challenging as it requires a deeper understanding of dynamical systems. Furthermore, when the time is discrete, Kalman observability separates into two different notions: observability and reconstructibility. The former characterises the reconstruction of the initial state of the system (i.e. 0 ) and the latter the reconstruction of the current state (i.e. ).

In this section, we will start with a formalisation of the notion of measurement and sensors for AC. This will allow us to define observability and reconstructibility for CA. We will also present a third characterisation called adaptability that serves as a link between these two notions.

State Representation of Cellular Automata

In classical control theory, the state representation is used to represent the studied system by including the notion of input and output. The best-known state representation is the one describing a linear time-invariant (LTI) system:

+1 = + = + (2.15)
, and are vectors that respectively represent the state, the output and the input of the system at time . is called the state vector, the output vector and the input vector. , , and are matrices that described the behaviour of the system. is called the state matrix which represents the dynamic of the system. is the input matrix which describes how the input impact the system. is the output matrix that describes how the system is measured. And is the feedforward matrix which represents the direct impact of the input on the output.

Within the scope of this work, we are only interested in the observation of systems, so there is no input (i.e. = 0), the simplified state representation is:

+1 = = (2.16)
In many cases, the considered system is not linear, so the linear state representation cannot work. The state representation for non-linear systems may be given as:

+1 = ( ) = ℎ( ) (2.17)
where the map describes the evolution of the state (state dynamics), while ℎ is the output map. Equation (2.18) describes the non-linear state representation adapted for the observation of CA. The state of the system is the configuration and its evolution is determined by the global transition function . The output operator represents the sensor network and represents the measurements taken by the sensors at time .

+1 = ( ) = ( ) (2.18)
With this representation, the state of the CA at time can be calculated from the initial configuration 0 using which represents the composition of times:

= ( 0 ) = ( ( 0 )) (2.19)
The definition of and is the subject of the following section where the notions of sensors, measurements and output operators will be discussed for the observation of cellular automata by a mobile sensor network.

Sensors, Measurements and Output Operator

Sensors play an important role in the observation of systems. It is through the information provided by them that the state of the system can be reconstructed. In all this work, we consider sensors as mathematical objects capable of measuring a part of the system. The reality is quite different, sensors are often very complex parts and require work in different disciplines, both in physics to convert the measured value into an electrical signal, and in signal processing to amplify, quantify, and filter the measurement. In addition, the sensor has to be adapted to the application: a temperature sensor for a freezer is not the same as one that measures the temperature of the Sun. For this reason, we will consider sensors only as mathematical entities measuring the ( ) state of a cell. For example, in the case of the Karafyllidis and Thanailakis forest fire spread model, the cell state is the biomass consumed. This value could be obtained from temperature sensors placed on trees, from satellite imagery of infrared radiation or from any other method. We will consider all these methods as one sensor, the sensor that measures the consumed biomass.

Before discussing measurements we need to define the notion of sensors, in particular its position (i.e. the position of these measurements) in relation to the CA model of the observed system. A sensor can measure the state of several cells at once, as shown in Figure 2.10, therefore we define L ⊂ L as the set of cells measured by the sensor . Moreover, several sensors can measure the system at the same time, so we define the set of all measured cells L is defined by the union of the sets of measured cells of all sensors as presented in definition 2.3. Definition 2.3 (Sensors). We denote , ∈ 1; , the sensor measuring the states of a set of cell L and , the set of sensors that observes the set of cells L ⊂ L with:

L = =1 L
(2.20)

On several occasions we will consider mobile sensors, that is sensors which have the ability to move or to change their measurement area. In this case, the set of cells observed by a mobile sensor evolves in time. We adapt then definition 2.3 by adding the time dependence. L , will denote the set of cells measured by the sensor at time , while L , denotes the set of all cells, measured by all the sensors, at time . When using a sensor network, it can be considered that the network is dynamic. Sensors may have been added to the network while others may be defective and no longer being able to take measurements. In general, it must be possible to consider that sensors can enter and leave the network, which has an impact on the measured cells. In this case, the set of sensors can evolve over time (if sensors enter or leave the network). However, it can also be considered that a sensor of the network can be inactive and in this case the set of sensors does not change but the set of observed cells does. Therefore, the expression of the set of observed cells is defined by :

L , = =1 ( , L , ) (2.21)
where , ∈ {0, 1} equal 0 if the sensor is inactive at time and 1 if it's active. The operator is defined by: : {0, 1} × P (L) → P (L)

, L ↦ → L := ∅ if = 0 L else (2.22)
At each time step, sensors take measurements on all the measured cells and return their state. These measurements are represented by the output vector which, in the same way as the configuration, describes the state of the measured cells at time . We define the sensor measurement operation on the system by the output operator which constructs the measurements from the measured system state .

Definition 2.4 (Output Operator). The output operator maps, at each time , the state of the cellular automaton A to the output vector ∈ O = S L :

:

S L → O ↦ → := (L , ) (2.23)
where (L , ) denotes the state of all cells in set L , at time .

Remark 2.2. In some cases, the sensors do not measure the state of a particular cell but a value from several cells. For instance, in the example on the CA RNG (see section 5.4 on page 129), the sensor measures the sum modulo 2 of all the cells in the CA. Only one value is returned by the sensor but it depends on all cells. Therefore, definition 2.4 cannot be applied and we must generalise as:

: S L → O ↦ → := ℎ (L , ) (2.24)
where ℎ is the function that converts the cell state into a measure.

In general, when observing a system, making a single measurement is not enough to know the state of the system. Measurements must be taken regularly, with a given time step (sampling) and only after a certain period of time, the number of measurements becomes sufficient to determine the current or initial state of the system. The vector composed of the successive output vectors (measurements) generated by the output operator is called an output sequence. The output sequence spanning from 0 to is noted Θ 0, = ( 0 , 1 , . . . , -1 ).

For the analysis of observability, whose criterion will be defined in the next section, we will need to study all possible output sequences. In this case, we derive from the state equation (2.19) the application Θ which constructs the output sequence Θ 0, from the initial configuration 0 by :

Θ : 0 ↦ → Θ 0, = ( 0 ( 0 ), 1 • ( 0 ), . . . , -1 • -1 ( 0 )) (2.25)
Similarly to what has been done for definition 2.1 of CA, we define the sensor network H which represents the set of sensors , the measured cells L and the output operator .

Definition of Observability and Reconstructiblity

Observability and reconstructibility, as defined by [START_REF] Emil | Mathematical description of linear dynamical systems[END_REF], determine whether or not 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 since 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 (as shown in section 5.3 on page 122).

An initial configuration 0 is considered observable if from the measurements taken by the sensors (i.e. the output sequence Θ ( 0 )) it is possible to uniquely identify 0 . In other words, the output sequence Θ ( 0 ) must be unique to 0 . Moreover, if all configurations of the CA are observable then the CA is considered observable. Formally, we can define the observability of a CA A as follows.

Definition 2.5 (Observability). A cellular automaton

A is observable by a sensor network H at time if and only if:

∀ 0 , 0 ∈ S L , Θ ( 0 ) = Θ ( 0 ) =⇒ 0 = 0 (2.26)
This definition of observability is equivalent to the injectivity of the output sequence Θ . Therefore, proving that a CA is observable by sensors is equivalent to proving the injectivity of the output sequence.

Reconstructibility can similarly be defined as the ability to reconstruct the current state = ( 0 ) from the output sequence Θ ( 0 ). However the formulation of definition 2.6 is not the injectivity of Θ but the injectivity of Θ with respect to 3.

Definition 2.6 (Reconstructiblity). A cellular automaton

A is reconstructible by a sensor network H at time if and only if:

∀ 0 , 0 ∈ S L , Θ ( 0 ) = Θ ( 0 ) =⇒ ( 0 ) = ( 0 ) (2.27)
These two definitions are the basis for observation as they ensure that the initial or current state can be reconstructed. It will be necessary to check before the observation phase that the chosen sensor network (by considering the positions or trajectories of each sensor) allows observability and reconstructibility.

Remark 2.3. In the case where the CA is reversible, then observability and reconstructibility are equivalent notions. Indeed, with reversibility it is possible to find 0 from because each configuration has a unique antecedent by . This also results from proposition A.3 on page A-3 and the injectivity (reversibility) of (and by extension .).

While studying the algorithmic complexity of computing observability of Boolean networks (a notion presented in detail in section 3.3.1), [START_REF] Laschov | Observability of boolean networks: A graph-theoretic approach[END_REF] present an observability criterion for an observability graph, an augmentation of the state transition diagram with the measurements made by the sensor. To be observable, the graph must satisfy two conditions: no configuration has two predecessor configurations with the same output; all cycles generate different output sequences. These two conditions are presented in detail in section 3.3.1 but we will focus here on the first one which can be formally written as: Definition 2.7 (Adaptability (or Laschov property)). A sensor network H is adapted for the observation of a CA A if and only if:

: ∀ 0 , 0 ∈ S L and 0 ≠ 0 , ( 0 ) = ( 0 ) =⇒ ( 0 ) ≠ ( 0 )
(2.28)

Laschov et al presented this condition as a criterion of observability but it turns out that this condition is not necessary for reconstructibility (see proposition 2.1). Therefore, we generalise this condition as a property of a sensor network with respect to a CA. This condition makes it possible to check before the observability computation that a sensor network H is adapted to the observation of a CA A. In some cases, this property can even be used to condition the placement of sensors.

Proposition 2.1. Let A a cellular automaton and H a sensor network. The following assertions are true:

(a) If H is not adapted to the observation of A then A is not observable by H for any > 0.

(b) If H is adapted to the observation of A and A is not observable by H for > 0 then A is not reconstructible by H at time .

Proof. Proof of (a): Suppose that H is not adapted to the observation of A, then there exists 0 , 0 ∈ S L and 0 ≠ 0 such that

( 0 ) = ( 0 ) ∧ ( 0 ) = ( 0 ). Let =⇒ ( 0 ) = ( 0 ) ∧ ∀ > 1, ( ( 0 )) = ( ( 0 )) = ( -1 ( 1 )) =⇒ ∀ > 0, Θ ( 0 ) = Θ ( 0 ) =⇒ For any > 0, A is not observable by H
Proof of (b): Suppose that A is not observable by H for > 0, then there exists

0 , 0 ∈ S L such that Θ ( 0 ) = Θ ( 0 ) ∧ 0 ≠ 0 . Then: ∀0 ≤ < , ( ( 0 )) = ( ( 0 )) ∧ 0 ≠ 0
However, with the contraposition of (2.28) we have:

∀ 0 , 0 ∈ S L and 0 ≠ 0 , ( 0 ) = ( 0 ) =⇒ ( 0 ) ≠ ( 0 ) Hence: ∀0 ≤ < , +1 ( 0 ) ≠ +1 ( 0 ) ∧ 0 ≠ 0 Especially for = -1, we have ( 0 ) ≠ ( 0 ) so: Θ ( 0 ) = Θ ( 0 ) ∧ ( 0 ) ≠ ( 0 )
This proves that A is not reconstructible by H at time The proposition 2.1 guarantees, before the calculation of the output sequence, whether or not the sensor network allows observability. When the proposition allows it but observability is not ensured, then it is unnecessary to evaluate the reconstructibility. Therefore, we only evaluate reconstructibility when the adaptability property does not hold. Moreover, when the CA is reversible, i.e. is injective (there is no 0 , 0 such that 0 ≠ 0 ∧ ( 0 ) = ( 0 )), the property is always satisfied and thus all sensor networks are adapted for observation (but does not necessarily ensure observability).

In the case of a time-dependent sensor network H , definition 2.7 cannot be applied, it should be verified that the output operator is suitable for all times. In that case, we propose the following definition.

Definition 2.8. A time-dependent sensor network H is adapted for the observation of a CA A at time if and only if:

: ∀ , ∈ (S L ) and ≠ , ( ) = ( ) =⇒ ( ) ≠ ( ) (2.29)
Given this property , the output operator is adapted to the observation over a time horizon if the following property

= 0 ∧ 1 ∧ • • • ∧ -1 (2.30) holds.
Only property (b) of proposition 2.1 holds in the case of a time-dependent sensor network. Indeed, the property (b) is easily proved because if we have then is true for all < . However, property (a) only holds when ¬ 0 . If we assume 0 ∧¬ 1 then ∀ ≥ 1, ( ) = ( ) (see the proof (a) of proposition 2.1) although no evidence is present for 0 ( 0 ) = 0 ( 0 ), which might be sufficient to guarantee observability. Therefore we define proposition 2.2 by: Proposition 2.2. Let A a cellular automaton and H a time-dependent sensor network. The following assertions are true:

(a) If H is not adapted to the observation of A at time = 0 then A is not observable by H for any > 0.

(b) If H is adapted to the observation of A for any time 0 ≥ < and A is not observable by H for > 0 then A is not reconstructible by H at time .

CONCLUSION

Throughout this second chapter, we have laid the foundations for the observation of cellular automata (CA) that will be used in the following chapters. In the first part of this chapter, we presented in detail the definition of CA from El Yacoubi. From this definition, we have presented several families of CA that will be used in chapters 3 to 5 for the presentation of different observation criteria. Among these, we will study in particular the additive (or affine) cellular automata (ACA) at the beginning of chapter 3 and the elementary cellular automata (ECA) throughout chapter 4.

In the second part of this chapter, we have formally defined all the tools necessary for the observation of CA. First, we defined the notions of sensors and the output operator, which allows the use of a sensor network, containing both static and mobile sensors. Then, we defined the notions of observability, reconstructibility and adaptability for CA. Observability and reconstructibility are concepts from "classical" control theory that have been adapted to CA. Whereas adaptability is a notion defined by [START_REF] Laschov | Observability of boolean networks: A graph-theoretic approach[END_REF] as a criterion for observability of Boolean networks (BN), it has been translated as specific notion for the observation of CA.

The main contributions of this chapter are the definition of tools for the verification of observability and reconstructibility and the generalisation of the Laschov criterion by defining adaptability as an observation tool. The definition of observability and reconstructibility have been presented in several publications (Plénet et al., 2020a(Plénet et al., , 2022a)). The discussion on adaptability has not been published yet.

In the following chapters, we will use the definitions made in this chapter to provide methods for observing CA. The criteria of observability and reconstructibility are studied in chapter 3. The chapter 4 focuses on state estimation through CA synchronisation, without checking for observability and reconstructibility. In the previous chapter, we presented the definition for observability, reconstructibility and adaptability. However, we did not provide any useful method to verify those properties. In this chapter we present different methods to check verify those three criteria. Firstly, for ACA and secondly for non-linear CA.

CHAPTER 3

Observability and Reconstructibility

RÉSUMÉ

Dans le chapitre précédent, nous avons défini les automates cellulaires, ainsi que des notions d'observabilité et de reconstructibilité qui s'appliquent à ceux-ci. Dans ce chapitre, nous allons donner des critères qui permettent de vérifier à la fois l'observabilité et la reconstructibilité pour certaines familles d'automates cellulaires. Dans un premier temps, nous étendrons le critère d'observabilité classique de Kalman aux automates cellulaires additifs. Nous donnerons aussi un critère de reconstructibilité pour cette famille. Ensuite, nous utiliserons la représentation par graphe de transition d'état, ainsi que des résultats de l'observabilité et de la reconstructibilité des réseaux booléens, pour proposer un algorithme permettant de vérifier l'observabilité et la reconstructibilité des automates cellulaires non linéaires (non additifs). Finalement, nous donnerons un critère d'observabilité régionale et de décentralisation de l'observabilité pour les automates cellulaires non linéaires.

ACA are linear systems with a finite number of variables. We can therefore apply some results from the control theory of linear time invariant (LTI) systems. However, we must be careful as we are dealing with finite-state variables. We present the Kalman rank condition for observability of ACA. We present a similar condition for reconstructibility and adaptability.

In the second part, we study non-linear CA by making them Boolean networks. Therefore, we adapt the work made on observability and reconstructibility of Boolean network to non-linear CA. The computational complexity of this method makes it impossible to apply it on large CA (more than a few cells). We present two different approaches to reduce the complexity. The first use some condition on the initial configuration and the second uses a decentralisation of the observability or reconstructibility.

KALMAN CRITERION FOR ADDITIVE AND AFFINE CELLULAR AUTOMATA

The [START_REF] Emil | Mathematical description of linear dynamical systems[END_REF] rank condition (or Kalman criterion) is a necessary and sufficient condition for a linear system to be controllable. Due to the duality of control and observation, this condition also applies to observability. The obtained observability condition is then based on the full rank of the observability matrix, which ensures the injectivity of the output sequence. Initially defined for linear time invariant systems, many other types of systems such as discrete-time systems [START_REF] Sarachik | Controllability and observability of linear discrete-time systems[END_REF] have a Kalman condition for controllability and observability. In this section, we propose an extension of the Kalman observability condition for ACA, and corresponding criteria for reconstructibility and adaptability. Finally, we present numerical methods for the verification of observability and reconstructibility for CA with a large number of cells.

Affine and Additive State Representation

In order to apply the Kalman criterion, we need a linear state space representation similar to the one presented in equation (2.16). In addition, we also need to be able to express the output sequence (2.25) with a matrix representation in order to verify its injectivity. We can extend the ACA to an affine sensor network when the corresponding output operator is an affine map. Such an affine output operator can be written as

: S → S ↦ → = + =          1,1 1,2 . . . 1, 2,1 2,2 . . . 2, . . . . . . . . . . . . ,1 ,2 . . . ,          •          ( 1 ) ( 2 ) . . . ( )          +          1 2 . . .          (3.1)
Note that, in many scenarios, sensors directly measure the state of a cell and therefore the weights , of the matrix are ones and the constants are zeros. Using the global transition function of an ACA (2.12), together with the affine output operator (3.1), the state-space representation of the ACA extended with its affine sensor network reads:

+1 = + = + (3.2)
We can express both and as a function of the initial configuration 0 :

= 0 + -1 = 0 + -1 + (3.3) with = =0
Finally, by adapting the definition of the output sequence (2.25) with the previous formulation, we can give the matrix writing for the output sequence Θ . Definition 3.1 (Affine Output Sequence). The output sequence Θ can be represented in affine form using the affine forms of the transition function and the output operator. We note the output sequence for outputs:

=          0 1 . . . -1          =          0 1 . . . -1 -1          0 +          0 1 0 + 1 . . . -1 -2 + -1          Γ = 0 + Γ (3.4)
where is called the observability matrix and Γ is a constant vector. The linear map represented by the observability matrix carries the injectivity property of the output sequence and therefore the observability property.

Example 3.1

In order to illustrate the results given in this section, we will apply them in a simple and didactic example where the necessary calculations will be detailed.

In this first example, we will define the CA and the sensor networks which will also be used in examples 3.2 and 3.3 for the verification of observability and reconstructibility. In order to be able to detail the calculations, the and matrices, whose sizes depend on the number of cells in the CA, must remain "readable". Therefore we decided to use the one-dimensional ACA with 8 cells defined by:

• L = {0, 1, . . . , 7}, a one-dimensional lattice of 8 square cells.

• S = {0, 1, 2, 3, 4}, a set of = 5 states. We have chosen as a prime number in order to apply observability and reconstructibility.

• N ( ) = { -1 , , +1 }, the neighbourhood of cell , with the periodic boundaries conditions -1 = 7 and 8 = 0 .

• :

(N ( )) ↦ → +1 ( ) = 2 • ( -1 ) + 3 • ( ) + 1 • ( +1 ) + 4,

an affine transition function

In order to obtain the matrix form of the CA evolution, we will use the definition of the matrix from (2.11). The weight , are derived from the weight of the local expression of :

∀ , ∈ L, , =            3 if = 2 if ≡ -1 mod 1 if ≡ + 1 mod 0 else
Therefore, we obtain the following matrix formulation: 4) +1 ( 5) +1 ( 6) +1 ( 7)

+1 = + =                 +1 ( 0 ) +1 ( 1 ) +1 ( 2 ) +1 ( 3 ) +1 (
                =                 3 1 0 0 0 0 0 2 2 3 1 0 0 0 0 0 0 2 3 1 0 0 0 0 0 0 2 3 1 0 0 0 0 0 0 2 3 1 0 0 0 0 0 0 2 3 1 0 0 0 0 0 0 2 3 1 1 0 0 0 0 0 2 3                 •                 ( 0 ) ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 )                 +                 4 4 4 4 4 4 4 4                 F .
. Example of evolution of the ACA from the initial configuration 01004324 for 15 time steps. Time is going rightward.

In order to illustrate the use of both mobile and static sensors, we will define H (1) and H (2) , two sensor networks. H (1) describes two static sensor that measures the left-end and right-end cells. H (2) describes a mobile sensor that observes the left-end cell but moves to the right cell (with a loop due to the periodic boundaries) at every time steps. The measurement sets of H (1) and H (2) are denoted respectively (1) and (2) :

• L (1) = { 0 , 7 } • L (2) , = { | with = mod 5}
Both sensor networks directly measure the state of the cells. Thus both (1) and

(2) are additive output operators which satisfy definition 2.4. Their corresponding matrices can be written respectively as:

• (1) : = 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

• (2) :
-0 = 1 0 0 0 0 0 0 0

-1 = 0 1 0 0 0 0 0 0 . . . -7 = 0 0 0 0 0 0 0 1
In this first example, we presented a one-dimensional ACA as well as two sensor networks, one of which is time-dependent. Later, we will study observability (example 3.2) as well as reconstructibility (example 3.3) for those sensor networks.

Conditions for Observability and Reconstructibility

In this section, we present theorems 3.1 and 3.3, both derived from the Kalman condition of classical control theory, which provide characterisations respectively for observability and reconstructibility. Each of these two theorems is accompanied by a corollary that allows either the reconstruction of the initial or the current state when respectively observability or reconstructibility is satisfied.

Theorem 3.1 (Kalman Condition). Let A and H be an ACA and time-dependent sensor network, with the associated matrices respectively denoted and .

The ACA A is observable by the sensor network H if and only if there exists a time > 0 such that:

=          0 1 . . . -1 -1          = (3.5)
The following proof demonstrates theorem 3.1 for an affine CA and an affine sensor network. For additive CA or sensor network, the proof is essentially the same with the only difference that the constants and are zero vectors.

Proof. Let A be an affine CA with and its associated matrix and constant vector. Let H be a time-dependent affine sensor network associated with the matrix and the constant vector . Then, let 0 ∈ S be the initial configuration and = 0 1 . . .

-1 the output sequence generated by the sensor network such that = 0 + Γ . Considering the definition 2.5 of observability, then:

A is observable by H ⇐⇒ ∀ 0 , 0 ∈ S L , Θ ( 0 ) = Θ ( 0 ) =⇒ 0 = 0 ⇐⇒ ∀ 0 , 0 ∈ S , 0 + Γ = 0 + Γ =⇒ 0 = 0 ⇐⇒ ∀ 0 , 0 ∈ S , ( 0 -0 ) = 0 =⇒ ( 0 -0 ) = 0 ⇐⇒ ker = {0} ⇐⇒ = dim( ) -dim(ker ) =
In the general case, the number of measurements (i.e. the dimension of the output sequence) is not necessarily equal to the number of cells. As a result, the matrix is not a square matrix. It is therefore impossible to find the inverse of the observability matrix even if is full rank. There is, however, a pseudo-inverse (Ben-Israel and Greville, 2003, Chap 1) matrix † which acts as a left inverse such that † = . Using this pseudo-inverse, it is possible to state the corollary 3.1.

Corollary 3.1. If the Kalman criterion is satisfied, then it is possible to reconstruct the initial state by pseudo-inverting the observability matrix. Indeed, based on the formulation (3.4) we obtain

0 = † ( -Γ ) (3.6)
Proof. Consider an ACA A observable by an affine sensor network H such that ∀ 0 ∈ S , = 0 + Γ and = . To simplify the notations, we shall simply note and Γ to respectively represent and Γ . As = , it means that it exists such that = (but not necessarily = because is full column rank not full-row rank). We can find = † by computing the pseudo-inverse of . Using the equation (3.4) we find that:

= 0 + Γ ⇐⇒ † ( -Γ) = † 0 ⇐⇒ † ( -Γ) = 0 (3.7) If is full column rank, † = ( ) -1 . If is square then † = -1 .
A characterisation theorem, similar to theorem 3.1, may also be formulated for the adaptability property. Recall that a sensor network is said adapted for the observation of a CA when no configuration has two predecessors with the same output (see definition 2.7). In the case of ACA, the adaptability characterisation theorem may be formulated as follows.

Theorem 3.2. Let A and H be an ACA and affine sensor network, with associated matrices respectively denoted and . The sensor network H is adapted to the observation of the ACA A if and only if :

ker ∩ ker = {0} (3.8)
Proof. Let A an ACA and and its associated matrix and constant vector. Let H be a sensor network associated with the matrix and the constant vector . The adaptability condition (2.28) in definition 2.7, when applied to the state space representation (3.2) for ACA, reads:

∀ 0 , 0 ∈ S ∧ 0 ≠ 0 , 0 + = 0 + =⇒ 0 + ≠ 0 + ⇐⇒ ∀ 0 , 0 ∈ S ∧ 0 ≠ 0 , ( 0 -0 ) = 0 =⇒ ( 0 -0 ) ≠ 0 ⇐⇒ ∀ 0 ∈ ∧ 0 ≠ 0, 0 ∈ ker =⇒ 0 ∉ ker ⇐⇒ ker ∩ ker = {0}
Using theorem 3.2, it is possible to find conditions on the matrix of the output operator by carefully placing the sensors so that it respects the theorem. In example 3.2, in addition to checking whether or not the sensor networks H (1) and H (2) are adapted to the observation, an example is given to provide a condition on the position of the sensor for the sensor network to be adapted to the observation.

Example 3.2

In this example, we take the ACA and the two sensor networks of example 3.1 and we will check the observability. If it is validated, then we will reconstruct the initial state using the output sequences generated by the output operators on the execution of Figure 3.1.

Before assessing the observability, we must verify if the sensors are adapted to the observation of the ACA. Therefore we find the eigenvectors of ker which are

(1) =                 2 2 0 1 2 2 0 1                 ; (2) =                 3 1 1 0 3 1 1 0                
Considering , the vectors of the canonical basis of , we can write the vectors (1) and (2) as:

(1) = 2 0 + 2 1 + 3 + 2 4 + 2 5 + 7 (2) = 3 0 + 1 + 2 + 3 4 + 5 + 6
Thus every element of ker can be written in the form (1) + ( 2) with ( ; ) ∈ S × S. In the canonical basis, we obtain

= (1) + (2) = (2 + 3 ) 0 + (2 + ) 1 + 2 + 3 + . . . • • • + (2 + 3 ) 4 + (2 + ) 5 + 6 + 7
When a sensor directly measures the state of a cell, all these measurements are only sensitive to changes in that cell. Thus, the kernel of the output operator is composed of all the other cells. The eigenvectors of ker (1) are therefore 1 , 2 , 3 , 4 , 5 and6 . For (2) , these are all so that ≠ .

To guarantee the adaptability of the sensor network, it is necessary to find ker ∩ ker = {0}, thus it is necessary to be able to nullify the coefficients in front of the in the writing of for those which are not ker , i.e. those corresponding to the measured cells. If there exists some values of and , for which

(1) +

(2) ∈ ker and ( ; ) ≠ (0; 0), then ker ∩ ker ≠ {0} the adaptability is not respected. Finally, we can see that H (2) is not adapted to the observation whatever is, because there exists non-zero solutions for each of the vectors: 2, 1), (3, 4) and(4, 2) are solutions of 2 + = 0; (0, ≠ 0) is a solution of = 0 and ( ≠ 0, 0) is a solution of = 0. However, H (1) is adapted as the non-zero solutions are not compatible, (1, 1) is not solution of = 0. More generally, any output operator that observes a combination of at least two cells and , with mod 4, is suitable for the observation of this ACA.

(1, 1) is a solution of 2 + 3 = 0; (1, 3), (
Even if the sensor network H (2) cannot ensure observability, we will still compute the observability matrix (this will be useful when computing reconstructibility) and check its rank. First, we must decide on a time horizon in order to construct the matrix . Let = 4 (this is justified by the Cayley-Hamilton Theorem presented later on) for the static sensor and = 8 for the mobile one, we obtain the following expression for in the case of H (1) and H (2) :

(

1) =                
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 1 0 0 0 0 0 2 1 0 0 0 0 0 2 3 3 1 1 0 0 0 4 2 1 1 0 0 0 4 2 3 3 3 4 1 0 3 1 1 3 4 1 0 3 1 1

3                 • 0 +                 0 0 4 4 3 3 2 2                 (2) =                 1 0 0 0 0 0 0 0 2 3 1 0 0 0 0 0 4 2 3 1 1 0 0 0 3 1 1 3 3 4 1 0 2 1 3 0 1 0 2 2 2 0 1 0 0 3 0 0 4 1 4 3 1 1 4 3 1 2 0 4 0 3 2 4                 • 0 +                 0 4 3 2 1 0 4 3                
In the case of H (2) , the rank of the observability matrix is 7 which is not enough to ensure observability. The verification of the reconstructibility will be done in example 3.3. The computation of the rank must be done in modular arithmetic, which is not the case for the usual rank operators. Indeed, the observability matrix for H (2) is not full rank, although using the usual rank operator it would be full rank since its determinant is 5 (which is 0 in modular arithmetic modulo 5).

On the contrary, H (1) ensures the observability because the rank of its observability matrix is 8. We will now compute the † matrix in order to reconstruct the initial configuration.

In this case † is a square matrix, so we will use the inverse computed from the determinant and the adjugate matrix (transpose of the cofactor matrix) -1 = ( ) -1 • ( ). Knowing that the determinant is 4, its inverse is 4 because 4 • 4 = 1 mod 5. Thus, the inverse of is expressed by: †

= ( ) -1 • ( ) = 4 •                
4 0 0 0 0 0 0 0 3 2 4 0 0 0 0 0 3 4 1 2 4 0 0 0 0 4 2 3 4 2 4 0 4 0 3 4 2 3 0 3 3 2 4 4 0 1 0 0 3 4 0 2 0 0 0 0 0 4 0 0 0 0 0 0

                =                
1 0 0 0 0 0 0 0 2 3 1 0 0 0 0 0 2 1 4 3 1 0 0 0 0 1 3 2 1 3 1 0 1 0 2 1 3 2 0 2 2 3 1 1 0 4 0 0 2 1 0 3 0 0 0 0 0 1 0 0 0 0 0 0

               
With the corollary 3.1 and the † matrix, we are able to reconstruct the initial state 0 from the output sequence :

0 = † ( -) =                 1 0 0 0 0 0 0 0 2 3 1 0 0 0 0 0 2 1 4 3 1 0 0 0 0 1 3 2 1 3 1 0 1 0 2 1 3 2 0 2 2 3 1 1 0 4 0 0 2 1 0 3 0 0 0 0 0 1 0 0 0 0 0 0                 •                 0 4 3 0 0 2 0 0                 -                 0 0 4 4 3 3 2 2                 =                 0 1 0 0 4 3 2 4                
In this example we were able to verify the observability of the output operator H (1) and to reconstruct the initial state. However, the H (2) output operator does not guarantee observability, so we will check observability in example 3.3.

In the case of time-continuous linear systems, observability and reconstructibility are equivalent concepts (Antoulas, 2005, section 4.2.2). The Kalman criterion ensures observability. However, in discrete time, there are systems which are reconstructible but are not observable (see for instance the road traffic example in section 5.3 on page 122). For this reason we propose a new theorem, similar to the Kalman condition, that provides a necessary and sufficient condition for an ACA to be reconstructible.

Theorem 3.3 (Reconstructibility Criterion).

Let A and H be an ACA and affine sensor network. We denote , their matrix form. The ACA A is said reconstructible by the sensor network H if and only if there exists > 0 such that:

ker ⊂ ker (3.9)
Proof. Let A an ACA and and its associated matrix and constant. Let H be a time-dependent affine sensor network associated to the matrix and the constant at time . Then, let 0 ∈ S be the initial state and = 0 1 . . .

-1 the output sequence generated by the output operator such that = 0 + Γ .

Consider the definition 2.6 of the global observability, then:

(A, H ) is reconstructible ⇐⇒ ∀ 0 , 0 ∈ S L , Θ ( 0 ) = Θ ( 0 ) =⇒ ( 0 ) = ( 0 ) ⇐⇒ ∀ 0 , 0 ∈ S , 0 + Γ = 0 + Γ =⇒ 0 + -1 = 0 + -1 ⇐⇒ ∀ 0 , 0 ∈ S , ( 0 -0 ) = 0 =⇒ ( 0 -0 ) = 0 ⇐⇒ ⊂
Corollary 3.2, hereafter, provides a reconstruction of the current state from the output sequence and the observability matrix. Example 3.3 describes the process of constructing the matrix in the case of a one-dimensional ACA. This method can easily be extended to multidimensional ACA. Corollary 3.2. If the reconstructibility criterion is verified, then it is possible to find a matrix such that:

= ( -Γ ) + -1 (3.10)
And Penrose (1956) defines as a set of solution depending on :

= † + ( - † ) (3.11)
where vector is arbitrary and since O is not of full rank, its pseudo-inverse is obtained through the matrix of its singular value decomposition , Σ, and as † = Σ † .

Proof. Consider an ACA A (with a matrix and a constant ) reconstructible by an affine sensor network H such that = 0 + Γ and ker ⊂ ker .

As ker ⊂ ker , it means there exists a matrix such that = . With this property, we can find that:

= 0 + Γ ⇐⇒ ( -Γ ) = 0 ⇐⇒ ( -Γ ) + -1 = 0 + -1 ⇐⇒ = ( -Γ ) + -1
Example 3.3

In this last example, we will check the reconstructibility of the sensor network H (2) , defined in example 3.1, for the case = 8. We proved observability is not satisfied. To prove reconstructibility, we start by finding the eigenvectors of the kernels of and :

(

1) =                 0 3 1 1 0 3 1 1                 ; (1) =                 2 2 0 1 2 2 0 1                 ; (2) =                 3 1 1 0 3 1 1 0                
We can fairly easily see that (1) = (1) + ( 2) is a linear combination of the eigenvectors of ker . Thus ker ⊂ ker and H (2) ensures reconstructibility. We will therefore use corollary 3.2 to reconstruct the current state, namely 8 . However, we did not find any algorithm to compute the pseudo-inverse or the singular value decomposition using modular arithmetic. Nevertheless, to reconstruct the current state, we could always use a state estimator like the one presented in section 3.3.3.

Finally, through these three examples we were able to verify the observability and reconstructibility for ACA. We were able to show the use of both a mobile sensor and a "network" of two static sensors. In section 5.4 on page 129 we will present an example about random number generator attack, where the use of observability for ACA will find a more concrete and natural application.

Tools for the Verification of the Kalman Criterion

In this section, we present tools that aim to simplify the computations for observability and reconstructibility. The Cayley-Hamilton theorem is used to bound the time horizon in the observability calculation with a static sensor network (only the lower bound applies when using a mobile sensor network). Different tools are presented to assist in the numerical verification of observability and reconstructibility.

Cayley-Hamilton Theorem

In linear algebra, the Cayley-Hamilton theorem states that any square matrix (of size × ) over a commutative ring (in our case S) satisfies its characteristic equation, i.e.

is a linear combination of with ∈ 0; -1 . It can be coupled with the Kalman Condition to give an upper bound on the time horizon .

Theorem 3.4 (Cayley-Hamilton Theorem). Suppose a CA observed by a time-invariant sensor network (i.e. by a static sensor), the observability matrix is of size × . . For the matrix to be of full column rank, the time horizon is bounded according to:

≤ ≤ (3.12)
Proof. Let us prove the two inequalities separately:

Proof of ≤ : The Cayley-Hamilton theorem guarantees that the rank of will not increase beyond T = N as is a linear combination of the , for 0 ≤ ≤ .

Proof of ≥ / : For to have a rank of , it needs at least rows and columns, thus . ≥ . Remark 3.1. In the case of a mobile sensor (i.e. a time-dependent sensor network), only the lower bound of the theorem 3.4 stands true. The Cayley-Hamilton theorem does not apply because is a linear combination

+ + • • • + -1 and not of the type 0 + 1 + • • • + -1 -1
, where depends explicitly on the time value .

The Cayley-Hamilton Theorem is particularly useful to limit the amount of time horizons to consider. In example 3.2, for the first output operator (1) , the Cayley-Hamilton theorem states that is bounded between 4 and 8. Because of it, if the system was not observable at time = 8 then it would have been meaningless to consider a larger time horizon in the expectation that the additional measurements would provide additional information to guarantee observability.

Numerical Tools

When the number of cells of the CA becomes too large, it is impossible to build manually the matrices and do the computations of observability and reconstructibility. In this section, we propose a method for constructing the matrix as well as a description of the algorithmic complexity of the observability computation.

In the one-dimensional case, the matrix is often almost similar to a tridiagonal matrix (or with more diagonals if the neighbourhood is larger). The non-zero values outside the main diagonals are typically close from the angles of the matrix and related to the boundary conditions. Except for the case of reflexive boundary conditions, the matrix can be described as a Toeplitz matrix [START_REF] Robert | Toeplitz and circulant matrices: A review[END_REF], where the coefficients ± correspond to the weights used in the sum (2.8) 1 .

=                0 1 2 . . . . . . -1 -1 0 1 . . . . . . -2 -1 . . . . . . . . . . . . . . . . . . . . . . . . 1 2 . . . . . . -1 0 1 -( -1) . . . . . . -2 -1 0                (3.13)
The coefficient 0 corresponds to the weight of the central cell, to the cells on the right and -to the cells on the left. In the case of periodic boundaries, the weights are also periodic: -1 = -1 and -( -1) = 1 . In example 3.1, 0 = 3, 1 = 1 and -1 = 2. For reflexive boundaries, we may consider first a null boundaries CA and add the boundaries afterwards by considering the following matrix (for a neighbourhood of distance ):

= +                • 0 0 0 . . . . . . 0 ( -1) • -1 0 0 . . . . . . ( -2) • -2 0 . . . . . . . . . . . . . . . . . . . . . . . . 0 ( -2) • 2 . . . . . . 0 0 ( -1) • 1 0 . . . . . . 0 0 • 0                (3.14)
In most cases, the state of a cell is observed directly, i.e. each element of the output vector is the state of one of the cells of the CA. Therefore the matrix has only one non-zero element in each row at the position corresponding to the observed cell.

The rank of a matrix is usually computed by performing a Gaussian elimination in order to find the number of independent columns (or rows) that represent the rank of the matrix. As the operations use modular arithmetic, the Gaussian rank elimination must use modular arithmetic. In example 3.2, the rank of the observability matrix differs whether the rank is done in modular arithmetic or not. Standard Gaussian elimination has an asymptotic algorithmic complexity ( 3 ), but more efficient algorithms exist to compute the rank more efficiently. For instance, [START_REF] Ho | Fast matrix rank algorithms and applications[END_REF] propose an algorithm to compute the rank of a × matrix with an algorithmic complexity of ( -1 ), with ≤ 2.38. When the Gaussian elimination is applied to the rank of the observability matrix of size × . , the complexity is therefore ( -1 ). In this section we have been able to study the observability, reconstructibility and adaptability of affine and additive cellular automata. The Kalman rank condition of classical control theory has been adapted to ACA as an observability condition. The reconstructibility and adaptability conditions are based on the kernel of linear applications. The three examples presented provided an opportunity to detail the computations of the different conditions, but also to present the potential computational difficulties related to modular arithmetic. Finally, we discussed typical matrix representation for typical 1D ACA and matrix algorithm complexity issues for the computation of observability and reconstructibility tests.

Although the presented methods perform well in the context of ACA, few CA can be considered as ACA. Still inspired by the classical linear control theory, other issues could be worth studying for ACA. First, the development of a state estimator could be investigated. It would be necessary to ensure that the observability and reconstructibility criteria allow the convergence of the state estimator, as well as to adapt the estimation algorithms to take into account the modular arithmetic. Second, a linearisation method could be found which would make it possible to analyse the observability/reconstructibility of non-linear CA through corresponding results for their lineasized ACA. This generalisation of results which exists for the state space representation (the linearisation or indirect approach) would allow the use of the results developed here above for a much larger number of CA systems. However, in this thesis, we have instead chosen to exploit the discrete and finite aspect of CA in order to develop a direct approach for the observability and reconstructibility analysis for non-linear CA.

OBSERVABILITY AND RECONSTRUCTIBILITY FOR NON-LINEAR CELLULAR AUTOMATA

In the previous part, we have studied the observability and the reconstructibility of ACA. They represent a very small part of the existing CA: for instance, only 16 rules out of the 256 Wolfram's ECA can be considered additive or affine.

In order to study the observability and reconstructibility of non-linear CA (i.e. neither additive nor affine), we will not focus on the algebraic expression of the transition function as we have done with ACA. Instead, we will study the links between the configurations through the state transition diagram presented in Figure 2.8. This method has already been studied many times for the verification of the observability and reconstructibility of Boolean Networks (BN) [START_REF] Laschov | Observability of boolean networks: A graph-theoretic approach[END_REF]Cheng et al., 2010). In this section, we adapt these formulations to bounded CA and propose numerical methods to verify their observability and reconstructibility. We will start by briefly defining BN, their links with CA as well as the different observability and reconstructibility criteria that are available in literature for BN.

Observability and Reconstructibility of Boolean Network

Described by [START_REF] Stuart A Kauffman | Metabolic stability and epigenesis in randomly constructed genetic nets[END_REF], Random Boolean Networks (RBN) are historically used as a tool for modelling genetic circuits, a new concept on the behaviour of genes inside a cell discovered a few years earlier by Jacob and Monod (winners of the 1965 Nobel Prize in Physiology or Medicine). Since their creation, they have been widely used in biology and particularly for the study of biological systems [START_REF] Wang | Boolean modeling in systems biology: an overview of methodology and applications[END_REF]. It is only in the early 2000s that they start to be studied mathematically, through the study of fixed points or basins of attraction [START_REF] Albert | Dynamics of complex systems: Scaling laws for the period of boolean networks[END_REF]. Different variants of BN are appearing, such as Probabilistic Boolean Network (PBN) [START_REF] Shmulevich | From boolean to probabilistic boolean networks as models of genetic regulatory networks[END_REF] and Boolean Control Networks (BCN) [START_REF] Cheng | Controllability and observability of boolean control networks[END_REF]. The study of BCN by Cheng with the use of the semi-tensor product [START_REF] Cheng | Semi-tensor product of matrices and its applications to dynamic systems[END_REF] introduced Boolean Network to the control community in the 2000s. Since then, BN have been the subject of numerous studies on the controllability [START_REF] Cheng | Controllability and observability of boolean control networks[END_REF] and the observability [START_REF] Laschov | Observability of boolean networks: A graph-theoretic approach[END_REF].

In this section, we will present BN and the relation with CA. We will also present two observability criteria for BN, the first one using the semi-tensor product, a generalised matrix product, to give an algebraic condition for observability and the second one using the state transition diagram to give a structural condition on the graph in order to guarantee observability of the BN.

Presentation of Boolean Network

A Boolean network is composed of a set of Boolean variables whose state is described by a Boolean function (potentially different for each variable). This function uses the state of several other Boolean variables to compute the next state of the variable it represents. This interconnection between the variables realised by the Boolean functions can be represented as a graph (see Figure 3.2a) where the nodes represent the Boolean variables and the edges represent a dependency by the transition function. The graph is complemented by a system of state equations (see Figure 3.2b) that describes the algebraic expression of the Boolean functions. Because of the non-linearity (from the point of view of linear algebra) of the logical operators of the Boolean algebra (only the operators XOR and NOT can be considered as linear), it is difficult to study Boolean networks in an algebraic way. Many study methods, especially those of the basins of attraction and cycles, use instead the state transition diagram (see Figure 3.3), which describes the behaviour of the BN on the configuration graph. From the definition of BN, we quickly notice that Boolean CA are a particular case of BN [START_REF] Gershenson | Classification of random boolean networks[END_REF]. Indeed, the lattice and the neighbourhood represent the interactions between the cells of the CA. It is a particular case of Boolean network where the network must respect the topology of the lattice and the neighbourhood. The restrictive requirement of the Boolean function (i.e. two states) can be overcome by using a -ary logical function [START_REF] Cheng | Matrix expression of logic and fuzzy control[END_REF]. Therefore CA, even nonboolean CA, can be considered as Boolean networks. However, the state transition diagram will have more nodes, e.g.

for a logic with states and variables.

Semi-Tensor Product and Observability

Described by Cheng in the early 2000s, the semi-tensor product (STP) is a generalisation of the usual matrix product when the two matrices do not have compatible sizes.

Unlike the Kronecker product (tensor product) and Hadamard product (element-wise product), the STP is equivalent to the usual matrix product when the sizes of the two matrices match. In addition to its purely algebraic definition, the STP has very concrete applications such as control theory, to find a singular feedback linearisation, or to find a matrix representation of logical operators (what we will be doing thereafter) [START_REF] Cheng | Semi-tensor product of matrices and its applications to dynamic systems[END_REF].

In this section, we will present in detail the STP and how it is used to represent logical functions and more specifically BN. Then, we will present how Cheng and Qi use the state representation provided by the STP to verify the observability of BN. Finally, we present the drawbacks of using such a technique.

The semi-tensor product allows the product of two matrices ∈ × and ∈ × even when they do not have adequate sizes (i.e. = ) but requires that the sizes of the matrices are multiples of each other (i.e. ∃ ∈ N, = or = ). If this constraint is respected then the semi-tensor product is defined by definition 3.2 (an example of the detailed calculation is presented in example 3.4) and satisfies the associativity and distribution rule with respect to matrix addition. Definition 3.2 (Semi-tensor product [START_REF] Cheng | Semi-tensor product of matrices and its applications to dynamic systems[END_REF]). Let ∈ × and ∈ × . The semi-tensor product is defined by:

= ( ⊗ ) ∈ × , if = = ( ⊗ ) ∈ × , if =
where ⊗ is the Kronecker product and is the identity matrix in × .

In order to be able to use the STP for BN and CA, it is necessary to be able to model the logical expressions in a matrix form. [START_REF] Cheng | Matrix expression of logic and fuzzy control[END_REF] starts by defining a logical domain with states by:

= 0; -1 (3.15)
To use matrix expression each element ∈ is identified with a vector ∈ 1× as:

∈ ⇐⇒ = , with ∈ 0; -1
where is the -th column of identity matrix . Therefore, in a Boolean logic (i.e.

= 2) 0 corresponds to 0 = 1 0 and 1 to 1 0 1 . In 5-state logic, state 0 corresponds to the vector 0 = 1 0 0 0 0 and state 3 to 3 = 0 0 0 1 0 . Remark 3.2 (Difference from Cheng and Qi definition). In order to be consistent with the definitions of cellular automata given in chapter 2, we have adapted the definition of the domain. In their definition, Cheng and Qi uses the fractional values /( -1) instead of integer values, for the domain , in order to relate to fuzzy logic. Furthermore, the elements of were arranged in descending order. We reversed the order to correspond as well as possible to the configurations of the CA where 0 is the first value and -1 the last one (with respect to the usual order).

A basic -ary logical operator (an operator with operands) is a mapping :

× × • • • × →
which can be represented by a × logical matrix2 . The application of this operator to logical variables ( ) is done with the STP as follows: (1) , . . . , ( -1) )

( (0) ,
= (0) • • • ( -1) (3.16)
In addition to the basic logical operators, Cheng shows that any logical function can be modelled by a logical matrix of size × , where is the number of inputs to the function. This can be determined analytically with the help of the STP, the logic matrices of the basic operators as well as various tools such as reduction matrices (matrix aiming at reducing the order of a variable, for instance such as =

) or swap matrices (matrix which makes it possible to invert the variables, such as e.g. = ). We will not describe explicitly the procedure for the construction of this logical matrix, but the details of the operations to construct the matrix can be found in appendix B or in [START_REF] Cheng | Semi-tensor product of matrices and its applications to dynamic systems[END_REF]Cheng and Qi, 2010).

In [START_REF] Cheng | Controllability and observability of boolean control networks[END_REF], the authors present a method to write a BN with -logical variables ( ) in the form:

+1 = (3.17)
where is a × logical matrix and = 0 1

• • • -1
. This form provides a state representation for BN (and by extension CA) even when the logical functions used are non-linear. The construction of from logical expressions is performed in a similar way to . Cheng and Qi also propose a method for finding the logical functions from the logical matrix .

The state variable represents a logical vector that describes the state of the logic variables (see example 3.4). This vector represents the node of the state transition diagram of the system at time . Thus, plays the same role as an adjacency matrix and we can write = where is the adjacency matrix of the state transition diagram.

Example 3.4

Considering the Boolean network in Figure 3.3, we can represent its state when = 0, = 1 and = 1 by :

= = 1 0 0 1 0 1 = ( 1 0 ⊗ 1 0 0 1 ) • 0 1 0 1 =         1 0 0 1 0 0 0 0         • 0 1 0 1 =         0 1 0 0         0 1 =                 0 0 0 1 0 0 0 0                
From this representation, it quickly follows that the output operator of the sensor network H can be represented as a logical matrix as well. The logical matrix is of size × , where is the number of sensors. Each column of the represents the output associated with the configuration represented by the column (i.e. the number of the configuration). For example, if we observe the variable in the BN of Figure 3.2, then is 0 1 when the configurations are 100, 101, 110 or 111 and 1 0 otherwise. Thus the matrix can be written as follows:

= 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1
The state representation of the BN can be written as:

+1 = = +1 0 = = 0 (3.18)
The equation (3.19) defines the observability matrix from and . Each column of this matrix represents the output sequence associated with the configuration of the column. Thus, the observability criterion of theorem 3.5 follows which ensures that each output sequence (column) is unique. However, is not, unlike and , a logical matrix. The logical matrix corresponding to the output sequence is obtained by the product = 0 • • • -1 and by factoring by 0 . This operation is used to obtain the logic matrix associated to the output sequence but it is not necessary to calculate the observability.

=          . . . -1          (3.19)
Theorem 3.5 (Observability of Boolean Network [START_REF] Cheng | Controllability and observability of boolean control networks[END_REF]). The system (3.18)

is observable at time if and only if the observability matrix has all distinct columns.

The adaptability property of definition 2.7 also applies to BN. It is precisely for the observability of BN that [START_REF] Laschov | Observability of boolean networks: A graph-theoretic approach[END_REF] have given this criterion. In a logical matrix, the value of an application is given by its column, therefore the adaptability criterion is defined by the following proposition.

Proposition 3.1. Let be the logical matrix of a BN with variables and states. An output operator is adapted for the observation of the BN if and only if:

∀ , ∈ with ≠ , ( ) = ( ) =⇒ ( ) ≠ ( )
Reconstructibility is slightly more difficult to verify than observability. Indeed, it is necessary to make sure that for the configurations which have identical columns in also have an identical current state . In this case, the columns in must also be identical. We can therefore formulate the following theorem:

Theorem 3.6. The system (3.18) is reconstructible at time if and only if the matrices and satisfy the following property::

∀ , ∈ with ≠ , ( ) = ( ) =⇒ ( ) = ( )
To summarise, this method provides a state representation for BN and CA. However, the size of the matrices depends on the number of configurations and not on the number of cells of the CA, as it was the case for the previous section. If we consider the number of cells, the number of sensors, the number of states in the state space and the observation horizon, the matrices , and are respectively of size × , × and • × . Therefore, this method can hardly be applied if the lattice of the CA exceeds several dozen or hundreds of cells. [START_REF] Laschov | Observability of boolean networks: A graph-theoretic approach[END_REF] rewrote the results of [START_REF] Cheng | Controllability and observability of boolean control networks[END_REF] on observability and formulated an equivalent criterion using a structural condition on the state transition diagram to prove that verifying the observability of a BN is an NP-Hard problem. This means that there is no general method to check observability with a polynomial complexity depending on the number of Boolean variables (or cells in the case of CA), except for simplifications (like the case of ACA). In this section, we will present the Laschov observability criterion and relate it with the algebraic method presented previously.

Graph Condition for Observability

Laschov et al. merged together the state transition diagram and the output operator into an observability graph (see Figure 3.4). The graph associated with the state transition diagram is modified to include the output. The edges of the graph are coloured (have a certain value called colour) which represents the output of the system. The output sequence is then defined as the set of colours obtained during a graph run from the initial node. For example in Figure 3.4a, if the variable is the output and the initial node is 011 then the coloured output sequence is ( , ℎ , , etc.) which corresponds to the Boolean output sequence (0, 1, 0, . . . ). The observability criterion based on this observability graph is defined by theorem 3.7. However the notion of cycle in this theorem differs from the notion of cycle presented in section 2.2.4. The term cycle refers here to a sequence which is looped for example the cycle 2

→ 3 → 4 → 1 → 2 is considered different from the cycle 4 → 1 → 2 → 3 → 4.
If nodes 1 and 3 are associated with colour 1 and 2 and 4 with colour 2 then the two previous cycles have the same output sequence ( 2 , 1 , 2 , 1 , 2 ). It is, however, a single cycle in the sense of the definition made in section 2.2.4.

Theorem 3.7 (Observability of Boolean Network [START_REF] Laschov | Observability of boolean networks: A graph-theoretic approach[END_REF]). An observability graph is observable for some time > 0 if and only if does not satisfy any of the two following properties:

1. There exists a node with two input edges of the same colour.

2. There exist two cycles generating the same output sequence.

For example, we can quickly see that the observability graph in Figure 3.4a is not observable because the 000 node has two input edges that have the same colour (dashed). The second graph is, however, observable as there is no node that has the same input colour twice and the only two cycles (000 → 101 → 000 and 101 → 000 → 101) have different output sequence.

Unlike other observability theorems, theorem 3.7 does not give the time horizon from which the BN is observable, it only guarantees that it exists. In the proof of this theorem, Laschov et al use = 2 + 1 ( the number of vertices or nodes) as the upper bound of the time horizon. This time is however very large compared to the minimal observability time. For example, the observation graph in Figure 3.4b has a maximum time horizon of = 65 while it is observable for = 5 (the output sequences of 111 and 011 are only distinguishable from = 5).

The notion of reconstructibility is not addressed by Laschov et al but it follows from theorem 3.7 on observability. Indeed, property 1, "There exists a node with two input edges of the same colour", is not necessary for reconstructibility. This property is the equivalent of the adaptability property presented in definition 2.7. If a node has two inputs of the same colour, then it is not possible, from the point of view of the output sequence, to differentiate between these two nodes but they both have the same current node. Reconstructibility is therefore not affected. Property 2 is still necessary as two different cycles necessarily have a different current node (even if they are on the same attractor cycle from section 2.2.4).

Laschov et al. also proposed algorithms to check the two properties necessary for observability. Property 1 is evaluated with the logic matrices and as in proposition 3.1. For the second property, they rely on the Jungers and Blondel (2011) algorithm which allows to check if a graph has the property 2. This algorithm constructs another graph 2 whose nodes are pairs of distinct nodes of and two nodes are linked by the same colour. If 2 admits a cycle, then property 2 holds true for . The search for the cycle is performed by a breadth-first algorithm. For an observability graph with vertices and possible edge colours, the complexity of this algorithm is ( 4 ). The algorithmic complexity for a BN with variables, states per variable and measured variables is ( 4 + ).

The previous algorithm has exponential complexity (hence not polynomial) but there could be algorithms in polynomial time. Therefore, in order to prove that observability evaluation is an NP-Hard problem, Laschov et al. created a special BN whose observability graph is an -cycle with 2 colours (continuous, dashed) but only one node has the continuous colour. Thus, the observability problem for this BN can be reduced to a 3-variable Boolean satisfiability problem (or 3-SAT) which is a well-known NP-complete problem. Except in the eventuality where = (one of the millennium prize problems) and the observability problem can be reduced to an NP problem, there is no general solution in polynomial time. However, the NP-hardness does not prevent algorithms from being found in polynomial time under certain hypotheses (for example, when we consider only ACA).

In conclusion, this method allows the observability and reconstructibility of BN to be evaluated from the observability graph which is constructed from the state transition diagram and the sensor network. Like the algebraic method presented by Cheng and Qi the complexity of evaluating observability and reconstructibility is exponential as a function of the number of cells, but this method makes it possible to know whether a BN is observable without having to search, by trial and error, for a valid time horizon. The downside is that this method does not provide the observation horizon, which makes it difficult to apply this method to the monitoring of complex systems.

Binary Relation Representation of Cellular Automata

As we have seen in the previous section, CA can be seen as a special case of BN. Moreover, the observability and reconstructibility of BN have been widely studied for over two decades, either in an algebraic way with the use of logic matrices and the semi-tensor product [START_REF] Cheng | Controllability and observability of boolean control networks[END_REF], or in a structural way with the use of the state transition diagram [START_REF] Laschov | Observability of boolean networks: A graph-theoretic approach[END_REF]. These two representations are related: the logic matrix is merely the transpose of the adjacency matrix of the state transition diagram. The criteria which result from these different representations make it possible to check the observability of the Boolean network in various ways.

With these two representations, verifying the observability is algorithmically complex: Laschov et al. have shown that it is an NP-hard problem. Moreover, the algorithms which verifies the observability often depend on the number of configurations (it is the case for the theorem 3.5 where each column represents a configuration) which grows exponentially according to the number of cells. This exponential complexity prevents the use of the algorithm when this number of cells exceeds several dozens or hundreds.

In order to reduce both the algorithmic and memory complexity, we can represent the logical matrix by sparse matrices [START_REF] Buluç | Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks[END_REF], an advantageous formulation 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 configurations is ( ). The structural analysis of the graph, requiring to verify observability with theorem 3.7, can also have simplifications that reduce the complexity, or at least the computation time.

Even using sparse matrices, the calculation of observability or reconstructibility for CA becomes impossible when it exceeds a hundred cells. The objective is therefore to benefit from some properties of CA in order to simplify the computations of observability and reconstructibility. The first property concerns in particular CA with constraints on the initial configurations. 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 we consider that the fire can only start on one cell of the CA, the number of initial configurations to study goes from 3 5054 to only 5055. The second property is based on the ease of distribution of the computation of CA [START_REF] Emmanuel N Millán | Performance analysis and comparison of cellular automata gpu implementations[END_REF]. Indeed, when the number of cells is large, it could be more efficient to compute several times the local function than the global function once. Therefore the computation of the observability matrix is no longer performed from the product of and but from a large number of simulations of the CA. The output sequence of each initial configuration is evaluated independently and the measurements are from simulations of the CA (often performed on GPU).

In order to benefit from those properties, we propose a definition of observability and reconstructibility based on binary relations. It associates two elements, here the initial configuration 0 (or current configuration if we study the reconstructibility) and the associated output sequence Θ ( 0 ). When we build this binary relation, we add the pair ( 0 , Θ ( 0 )) only if the initial configuration 0 is part of the initial configurations to study. In this formulation, the calculation of Θ can be done by simulation or by matrix product using and according to what is more efficient. Therefore, we can define the observability binary relation R Θ and the reconstructibility binary relation RΘ by: Definition 3.3. The observability and reconstructibility binary relation R Θ and RΘ associated to the output sequence Θ is defined as follows:

R Θ = {( 0 , Θ 0, )| 0 ∈ W and Θ 0, = Θ ( 0 )} (3.20) RΘ = {( , Θ 0, )| 0 ∈ W and Θ 0, = Θ ( 0 ) and = ( 0 )} (3.21)
where W ⊂ S L represents the set of admissible initial configurations. Proof. For the observability condition, the theorem follows directly from definition 2.5 which represents the writing of the injectivity of Θ, since R Θ is the relational writing of Θ.

The reconstructibility condition (2.27) in definition 2.6 may be written, using the binary relation representation, as:

∀ 0 , 0 ∈ W, Θ ( 0 ) = Θ ( 0 ) =⇒ = ⇐⇒ ∀ , ∈ (W), RΘ ( ) = RΘ ( ) =⇒ = ⇐⇒ RΘ is injective
From the BN presented in Figure 3.2, we are able to construct the observability and reconstructibility relations. We will use the output operators presented in Figure 3.4, namely L = { } and L = { } with a time horizon = 5. Table 3.1 presents all the elements of the two relations R Θ and RΘ . As in the previous section, we notice that measuring the state of ensures observability contrarily to the measurement of the state of . Moreover in this example, we can also guarantee that measuring the state of ensures reconstructibility because identical output sequences are associated with the same current configurations. 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 algorithm 1 on the facing page that constructs simultaneously the relations R Θ and RΘ and also to check their injectivity during their construction.

L = { } L = { } (000,
When the algorithm detects that the observability or the reconstructibility is not verified, it has an exit condition without having to study all the initial configurations.

Similarly to the observability and reconstructibility relations, we could construct the adaptability relation R which associates the state 1 = ( 0 ) with the output 0 = ( 0 ). In order to guarantee adaptability, it is necessary that the relation R can be constructed without duplicates. Indeed, if there is a duplicate, then 0 and 0 exist so that 0 ≠ 0 and 1 = ( 0 ) = ( 0 ) and 0 = ( 0 ) = ( 0 ). However, as with algorithm 1, we evaluate observability and reconstructibility simultaneously, the adaptability property is not necessary. Indeed, if for a given configuration 0 observability is not verified but reconstructibility remains possible, then adaptability is not true (corollary of property (b) of proposition 2.1). In order to construct the observability relation, the output sequence is computed for each of the possible initial configurations 0 ∈ W. However, to obtain the output sequence Θ ( 0 ) we need the configurations from 0 to -1 , so we can take advantage of -1 to compute in order to build the reconstructibility relation. As for the evaluation of the injectivity, we use a specific data structure called Hashmap to record the relations R Θ and RΘ . This type of data structure stores 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 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. The first part has a complexity of ( ) where is the time horizon and is the complexity of the global transition function . If we consider that the global transition function is evaluated as the local function applied to all cells, then its complexity is of the order of ( ). However, due to the ease of parallelisation of these operations, especially on a GPU, then the computation time is largely reduced because a very large number of these operations (or even all of them) are evaluated at the same time when the computation is performed on a GPU. Moreover, the observability horizon is at worst of the order of in an observation problem. Indeed, if this horizon is much larger than , then the disturbance we are trying to estimate (a forest fire, a road traffic, etc.) has had time to propagate over the whole system before we are able to reconstruct it. This is even more true for dimensions greater than 1 where the dynamics propagates faster compared to the number of cells. The second part of the algorithm has a constant complexity of (1) as the operations of read and writes of Hashmap have both a complexity of (1). Finally, the total algorithmic complexity is ( 2 ) where is the number of admissible configurations.

If we consider that all initial configurations are studied (i.e. W = S L ) then the complexity of the algorithm is O (

2 ). Compared to the algorithm that verifies observability for affine CA presented in section 3.2.3, this algorithm has a greater complexity. The algorithmic complexity for verifying observability is polynomial for affine CA O ( -1 ) and exponential for non-linear CA O ( 2), with representing the number of cells, the number of sensors, the number of states and the time horizon.

State Estimator for Non-Linear Cellular Automata

In this section we will define a state estimator for non-linear CA in order to estimate the state of the CA from the measurements. It will be notably necessary for the decentralisation of the observation that we will present in the next section. The state estimator that we will present is similar to those that we can find in [START_REF] Yang | Redefined reconstructibility and state estimation for boolean networks[END_REF] and [START_REF] Braga-Neto | Optimal state estimation for boolean dynamical systems[END_REF]. It is defined for Boolean networks and provided an estimation of the current state of the system. We will see with theorem 3.9 that reconstructibility is necessary to correctly estimate the state of the system. We will first define the tools needed to build the state estimator and prove theorem 3.9.

Tools for the State Estimator

The state vector defined in section 3.3.1 for the observation of BN represents the configuration of the system at time . This state vector has a single 1 coordinate which represents the current configuration, while all other coordinates are 0. It may be extended to a vector with more non-zero coordinates to represent a set of configurations, and to coordinates which are greater than 1 to put different weights on some of these configurations. This extension is for instance widely used in graph theory with the adjacency matrix which is generalised to represent the number of paths between two nodes. Such an extended vector represents therefore an equivalent set of configurations which is explicitly given in the following definition.

Definition 3.4. The state vector can be written as a subset of S L by:

= { ∈ S L | | = ∧ ( ) = 1} (3.22)
where | is the decimal value of the configuration state (see section 2.2.4 on State Transition Diagram and Attractor) and ( ) is the -th element of the vector .

From this set, we can also compute the image sets of the functions , and Θ (simply by computing the function on each of the elements of ). For instance

+1 = ( ) = { ( )| ∈ } The set +1 = ( ) is equivalent to the state vector +1 =
. If is not reversible, then there exists 0 , 0 ∈ 0 and 0 ≠ 0 such that ( 0 ) = ( 0 ). In that specific case, the element corresponding to 1 = ( 0 ) = ( 0 ) in 1 will have the value 2, one for ( 0 ) and one for ( 0 ). We could normalise the result in order to have values in {0, 1}. However, in the case of the state estimation problem and algorithm, it will be useful to have these extended values (greater than one) to construct a good estimate of the cell state as it provides more information on the number of initial configurations that have converged toward 1 . In terms of set definitions, this means that 1 contains the configuration 1 twice, once for ( 0 ) and once for ( 0 ). This is a particular definition of a set with several iterations of the same element. We can adapt definition 3.4 to allow its use with non-unitary coefficients by using the following notation:

= { ∈ S L | | = ∧ ( ) ≥ 1}
For the construction of the state estimator, we will need an operation, similar to the intersection of the sets , for the state vectors . For this, we will use the Hadamard product (or element-wise product) which multiplies element by element the two operands (the two operands must have the same size). Therefore we propose the following to compute the intersection between the two set from the state vector: Proposition 3.2. Let and be two state vectors and , their set representations. The intersection between these two sets can be computed from the state vector with the help of the Hadamard product as: = Proof. Let be the set representation of = and . Equation (3.22) in 3.4 may be written with the set representations:

= { ∈ S L | | = ∧ ( ) • ( ) = 1} = { ∈ S L | | = ∧ ( ) = 1 ∧ ( ) = 1} = { ∈ S L | ∈ ∧ ∈ } = ∩
In the case where the vectors have non-unitary coefficients then the Hadamard product will multiply these coefficients. If a configuration appears twice in a set and twice in another set, the intersection with the Hadamard product will produce a set where this configuration appears 4 times. This is why we impose that at least one of the vectors use in the Hadamard product has unitary values. It will avoid increasing the coefficient in the intersection vector. In the next section, when we will study the state estimator, the reciprocal of the output operator ( ) is a state vector with unitary value, so we will be able to use the Hadamard product as an intersection operator.

Definition of the State Estimator

The state estimator is constructed from the measurements made on the system. The output which represents the measurement of the system is considered as an input to the state estimator. The latter represents the set of configurations that are consistent with the measurements made on the system. Thus, the set of estimated configurations ˆ evolves at each acquisition of a new measurement: all the configurations which are not compatible with the measurement are withdrawn from ˆ . Considering that at time = 0 the set of possible configurations is the set of admissible configurations ˆ 0 = W, we can therefore define the evolution of the state estimator as :

ˆ +1 = { ( )| ∈ ˆ ∧ ( ) = } (3.23)
Using the reciprocal function of the output operator , we can determine the set of configurations that have the output . In the case of a logical matrix, the reciprocal is the transpose of . Hence, ˜ = is the state vector that has, as its element, all configurations which have as their output. We simply adapt (3.23) in order to use ˜ the set representation of ˜ = :

ˆ +1 = { ( )| ∈ ˆ ∩ ˜ } (3.24)
From (3.24) we propose the definition 3.5 which adapts the state estimator in the form of a state representation. Definition 3.5. Let A be a CA defined by the logical matrix and observed by a sensor network H defined by the logical matrix . The estimation ˆ of the state is realised through the measurements by:

ˆ +1 = ( ˆ ) ˆ 0 = 1 (3.25)
where 1 is a column vector of size compose of 1.

The estimated state vector ˆ is a set of the estimated configuration of the system. From this we can estimate the state of the cell by using the output operator ( ) which measures the cell directly. The estimate of the cell equals ˆ ( ) = ( ) ˆ and is a column vector where each coordinate represents the number of configurations in ˆ that have the corresponding state value (state 0 for the first coordinate and so on). Example 3.5 hereafter details this for the BN of Figure 3.2.

Example 3.5

Consider the BN defined in Figure 3.2 and the estimated set ˆ = {001, 111, 101}. From ˆ we can easily see that the node has the state 1 for 2 out of the 3 configurations, the node for 1 out of 3 configurations and the node for every configuration. We can compute the same results from ( ) , ( ) , ( ) and ˆ which are defined by: ˆ = 0 1 0 0 0 1 0 1

( ) = 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 ( ) = 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 ( ) = 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1
From these elements we can calculate ˆ ( ) , ˆ ( ) and ˆ ( ) the estimates of cells , and at time by :

ˆ ( ) = ( ) ˆ = 1 2 =⇒ = 0 for 1 conf. and = 1 for 2 conf. ˆ ( ) = ( ) ˆ = 2 1 =⇒ = 0
for 2 conf. and = 1 for 1 conf.

ˆ ( ) = ( ) ˆ = 0 3 =⇒ = 0 for 0 conf. and = 1 for 3 conf.

Lemma 3.1. Consider an initial configuration, unknown to the state estimator, and the associated output sequence Θ at time > 0. The state estimator ˆ constructed from the output sequence corresponds to all configurations that have this output sequence. Formally we can write this as :

∀ 0 , ∈ S L such that = ( 0 ), Θ ( 0 ) = Θ =⇒ ∈ ˆ
Proof. By definition (3.23) implies that if ˆ respects lemma 3.1 then ˆ +1 also respects the lemma 3.1 because:

∈ ˆ ∧ ( ) = =⇒ ∀ ∈ 0, , ( ) = =⇒ Θ( 0 ) +1 = Θ +1
By definition, ˆ 1 respects the lemma 3.1 as Θ 1 = ( 0 ). Therefore, with an inductive reasoning, we conclude that the lemma 3.1 holds for all > 0.

From lemma 3.1 and definition 2.6 on reconstructibility, we know that at some point there is only one current configuration that respects the output sequence given as input to the state estimator. Thus we give the theorem 3.9 that guarantees perfect estimation of the system if the reconstructibility is insured. Theorem 3.9. If a CA is reconstructible at time then the state estimator of definition 3.5 gives a perfect estimate of the current state at time (i.e. ˆ = ).

This state estimator has two major problems. The first one is the use of logical matrices which implies an exponential complexity with respect to the number of cells. The use of the set representation ˆ permits to use the paradigm proposed in section 3.3.2 with the reduction of the plausible initial configurations. Even then, the state estimator is meant to be used during the observation phase, unlike observability and reconstructibility which are evaluated beforehand. In order to use the state estimator for monitoring complex systems, the computation time of an iteration (i.e. ˆ +1 from ˆ ) must be smaller (or even much smaller) than the time period of the system evolution.

The second problem is the robustness of the state estimator to error, and particularly to measurement error. Indeed if the sensors provide, at a given time , an erroneous measurement then the state estimator will not be able to correctly estimate the current state. The inverse output operator ( ) includes all the states that have as output, but as the measurement is incorrect, the current state of the system is not in ( ). This non-robustness to errors does not allow the use of this state estimator for physical system observation. To increase the robustness of the state estimator [START_REF] Guo | Optimal state estimation of boolean control networks with stochastic disturbances[END_REF] uses a stochastic output operator to model the probability of sensor error.

In this section we have given a state estimator for non-linear CA. We also proved that the state estimator converges to the state of the system when reconstructibility is satisfied. However, this state estimator has the same algorithmic and memory complexity problems as the study of observability and reconstructibility of BN itself. These complexity issues and the robustness problem do not allow the use of the approach for monitoring real large-scale physical systems.

DECENTRALISATION OF OBSERVABILITY AND RECONSTRUCTIBILITY

In the previous two sections, we were able to define observability and reconstructibility criteria for additive, affine and non-linear cellular automata. The Kalman criterion for ACA can easily be evaluated on a computer for CA for several thousand cells. In the case of non-linear CA, although further optimisations could be made, unless the number of plausible initial configurations is drastically reduced, it is simply impossible to evaluate observability beyond a hundred cells. In this section we will propose a method to reduce the algorithmic complexity by dividing the CA into many smaller CA.

Considering cellular automata as Boolean networks, the links between cells being determined by the neighbourhood, CA are not very connected (few links between cells). This is particularly true for one-dimensional CA where the number of links is 2 compared to 4 or 9 for two-dimensional CA (depending on the chosen neighbourhood). Therefore it seems possible to decompose the observability problem into smaller ones with the goal to drastically reduce the algorithmic complexity. The observability would be computed for each part and be extended to the whole CA. The complexity factor would be reduced from the size of the CA to the size of its part. To achieve this, sensors and subdivisions must be judiciously chosen to ensure observability or reconstructibility of any cell in the CA.

The distribution of observability and reconstructibility has recently been studied for large BN [START_REF] Zhang | Efficient verification of observability and reconstructibility for large boolean control networks with special structures[END_REF]. The authors grouped the highly connected nodes into sub-BN whose observability calculation is simpler. Interactions with other sub-BN are modelled as inputs as for BCN. In the case where the network composed of sub-BN is acyclic, the observability of all sub-BN implies the observability of the BN. In the cyclic case, the generalisation of the observability of the sub-BN to the observability of the initial BN is more complex. This method is very poorly applicable to CA because cells are mutually dependent on their neighbours, which directly implies a cyclic relationship between the cells of the CA.

In this section, we first propose a definition for the sub-CA used for decentralisation of observability and reconstructibility analysis. Then, we present a method adapted to the observation of one-dimensional CA (the cost for observation being too high for two-dimensional CA) as well as several ideas for improvements in the decentralisation of observability and reconstructibility.

Observability and Reconstructibility of Sub-CA

In order to reduce the algorithmic complexity, we will divide the observability problem into several observability problems of lower complexity. It consists in dividing the L lattice of A into several smaller lattice L ( ) ⊂ L. We call the CA defined on the subdomain L ( ) the sub-CA A ( ) of A.

Sub-CA do not have any more autonomous dynamics: they are no longer isolated. Their boundary conditions represent interactions with cells of the bigger CA and will be referred to as unknown boundary conditions. As these cells are not within the sub-CA, they belong to other sub-CA that estimate their values. Neighbouring sub-CA will thus mutually exchange the values of the boundary cells. The boundary conditions of the sub-CA can be considered as inputs and we can define the sub-CA as a CA with inputs. Definition 3.6. A sub-CA A ( ) over a domain L ( ) ⊂ L of a CA A is defined by (3.26) where ( ) and ( ) are respectively the configuration and the output of the sub-CA at time . ( ) represents the value of the boundaries cells at time . and have been adapted to include the subdomain L ( ) and the ( ) boundaries as inputs.

       ( ) +1 = ( ) , ( ) ( ) = ( ) (3.26)
These boundaries can a priori take any admissible state values at each time step. Therefore we have to define a new notion of observability and reconstructibility for CA with unknown boundary conditions. The observation of a system with unknown inputs has already been studied for linear systems [START_REF] Basile | On the observability of linear, time-invariant systems with unknown inputs[END_REF] but the results cannot be applied to non-linear CA. We therefore find another criterion using the finiteness of the set of possible inputs. For a specific evolution of the bigger CA, the boundary conditions of the sub-CA are well known and therefore the state configuration ( ) has a fixed trajectory. This trajectory may be different for each initial configuration of the bigger CA. This is the reason why we consider it necessary to check the observability or reconstructibility for each fixed boundary trajectory. We propose the following proposition for the observability or reconstructibility of a sub-CA.

Proposition 3.3. A sub-CA A ( ) with unknown boundary conditions is observable (reconstructible) by a sensor network H ( ) at time if and only if the sub-CA is observable (reconstructible) for every admissible boundary trajectories.

Proposition 3.3 guarantees observability and reconstructibility for the sub-CA A ( ) regardless of the initial configuration of the CA A. Thus the state of all the cells of the sub-CA is known at time . The corollary 3.3 follows immediately from this proposition. If the set of observable (reconstructible) sub-CA A ( ) covers the whole CA A (i.e.

L ( ) = L) then the set of cells of L are observable (reconstructible).

Corollary 3.3.

A CA A is observable (reconstructible) if there exists a set of observable (reconstructible) sub-CA ( ( ) ) ∈N such that ∈N L ( ) = L.

Remark 3.4. If the sub-CA do not cover the whole CA, then only a region of the CA is observable (reconstructible), we can speak of regional observability or reconstructibility [START_REF] Fekih | Observability and reconstructibility of probabilistic boolean networks[END_REF]. However, this is a special case of regional observability where the sensors are placed directly in the region to be observed and the dynamic of the system outside the region is not modelled (except through the boundaries). In some cases, sensors placed outside the region of observation ensure the observability of this region. Note also that some of the results for the regional controllability [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] of CA could be transposed to observability by duality of the two properties.

The placement of the sensors is more important in the case of the decentralised observation than in the classical approach because the state values at the boundary must then be either measured or estimated. In the case where an estimation is provided to the sub-CA, it may happen that the observable time horizon is not reached yet and the estimation is not yet perfect. We discuss this issue in section 3.4.3 when a probabilistic sub-CA model is used to cope with this uncertainty of the estimation. In the next section, we consider first the case with measured boundary cell state values.

Deterministic Method for Distribution

To ensure the observability or reconstructibility of a sub-CA with proposition 3.3, it is necessary to measure the value of boundary cells at each time step. Therefore, for each sub-CA we must at least measure cells that are boundaries for other sub-CA. However, more cells could be measured, in order to insure the observability or reconstructibility. The value of those measured cells are both used in the observability criterion and as the boundary for the neighbouring sub-CA.

For one-dimensional CA, the sensors can be placed directly on both sides of the sub-CA and thus act as a sensor for the sub-CA and as a boundary cell sensor for the neighbouring sub-observers (see Figure 3.5). 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 is not sufficient to ensure observability or reconstructibility, other sensors can be added within the sub-CA but, then, their sole purpose is to estimate the state of the sub-CA. This method significantly reduces the complexity of the observability of onedimensional CA because the subdivision reduces the number of cells whose observability needs to be checked. Consider a one-dimensional CA with cells and states. If we divide this CA in equal parts, then the number of initial configuration goes from to . However, we have to evaluate the observability for each possible boundary trajectory. For 2 boundary cells and a time horizon there are 2 possible boundary trajectories. Finally, the total number of operations to compute the observability is × 2 = +2 . If the sub-CA that compose the CA are not of the same size, then observability must be checked independently for each sub-CA which will increase the complexity linearly to the number of sizes.

This method works very well for one-dimensional CA because the size of the boundary is independent of the number of cells in the CA: there are always 2 boundary cells. However, in two dimensions (or more) the number of boundary cells increases with the number of cells. For a × sub-CA, there are 4 boundary cells for a Von Neumann neighbourhood and 4( + 1) boundary cells for a Moore neighbourhood. The more boundary cells there are, the more boundary trajectories have to be considered and the more operations are needed to assess the observability. For a × sub-CA with Von Neumann neighbourhood under a time horizon , there is 2 +4

operations. In addition, the minimal sensor density also increase compared to 1D CA. For a × sub-CA, it is necessary to measure the state of the 4( -1) cells on the edge which are boundary cells for the other sub-CA. The sensor density for a sub-CA is 4( -1)/ 2 against 2/ for a one-dimensional sub-CA of size .

Probabilistic Model for Estimated Boundaries

In order to use the decentralisation of observability and reconstructibility in the two-dimensional case, an alternative to the measurement of boundary cells must be found. The idea is to provide, to the sub-CA, only an estimate of the state of these cells. However, as long as the observation horizon is not reached (i.e. < ), the state of the sub-CA is not perfectly known, i.e. there are still several initial configurations which have the same output sequence Θ . Using the state estimator given in definition 3.5 we can deduce an estimate for the state of cell on the boundary. Giving a value for the boundaries based on the statistical majority will lead to not considering the minorities, certainly less probable but still existing. In order not to lose information in the process, the proportion of each state value should be provided for each boundary cell. This formulation leads necessarily to the modelling of the sub-CA which have several potential evolution depending on the proportion of the state of the boundaries. This is precisely the case for probabilistic CA (PCA) (see section 2.2.3 on Probabilistic Cellular Automata) where the estimated state of the boundaries is used as a probability. This leads not only to a new model for sub-CA but also to a new probabilistic approach to observability and reconstructibility.

Probabilistic observability differs from the observability given in definition 2.5 in that for a given initial configuration there may be several output sequences Θ( 0 ). In the probabilistic case, the objective is still the same: to identify the initial configuration from an output sequence, but this is more complicated due to the non-determinism of . In the case of probabilistic sub-CA, we have the advantage of having a deterministic output operator because the system we observe is deterministic (if we do not seek to handle measurement error as explain as the end of section 3.3.3). Fornasini and Valcher (2019) studied this special case (i.e. probabilistic and deterministic ) for probabilistic Boolean networks (PBN). They provided a definition for observability and two definitions for reconstructibility, one strong and one weak. Several algorithms to check these three criteria were also given. Definition 3.7 (Observability and Strong/Weak Reconstructibility). Fornasini and Valcher (2019) define the following notion for observability and reconstructibility of PBN.

• A PBN is observable at time if for every admissible output sequence Θ the initial configuration 0 can be uniquely identified.

• A PBN is strongly reconstructible at time if for every admissible output sequence Θ the current configuration can be uniquely identified.

• A PBN is weakly reconstructible at time if for every admissible output sequence Θ the intermediate configurations , for 0 < < , can be uniquely identified.

The observability and the strong reconstructibility are similar to those we defined in section 2.3.3. Weak reconstructibility, on the other hand, is a proper notion due to the non-determinism of . Indeed, if we know for < then we do not necessarily know because of the non-determinism of . The approach used to model PBN is similar to (3.18). The PBN logical matrix is defined as a discrete function which is equal to a deterministic logical matrix with a probability as follows:

=        1 with a probability 1 . . .
with a probability (3.27)

As sub-CA models a deterministic system with unknown input by a probabilistic model, there are as many different as there are different inputs. Thus inputs for a sub-CA with boundary cells and states.

To verify observability and reconstructibility, Fornasini and Valcher do not check if all the output sequences of the initial configurations are different but they construct the set X(Θ ) which contains all initial configurations 0 which have Θ as output sequence. X(Θ ) is constructed as the intersection of X ( ) which represents the set of configurations which have as their -th output. To do this, they use to find all the configurations that have as output and then they use the mapping P to find all the antecedents 0 of the configurations . Therefore X(Θ ) is constructed as:

X(Θ ) = -1 =0 X ( ) = -1 =0 P ( ) (3.28)
If X(Θ ) is either empty or a singleton then the output sequence is uniquely associated to a single configuration. This approach works well algorithmically as there are many exit conditions (e.g. if for a given output sequence, X has more than two or more elements then observability is not checked). However, the construction of the predecessors with P can be complex when the number of matrix is large. Similarly, the number of possible output sequences is at least as large as the set of initial configurations, which necessarily results in high computational complexity for general CA.

Once observability or reconstructibility has been verified, the state of the boundaries must be estimated. The state estimator is made in a similar way as the deterministic one. The main differences are that the logical matrices are Markovian matrices and that the weights are probabilities. For the state vectors, these are the probabilities of each configuration and for the matrices they are the probabilities of transitions from one configuration to another (i.e. =

). However, it is necessary to normalise the Hadamard product so that the result remains a probability vector. Convergence to a unique current configuration has not been demonstrated in this work but we have the intuition that strong reconstructibility is a sufficient condition. Weak reconstructibility does not seem to be relevant for this state estimator but we believe it can be adapted for it.

In conclusion, we have shown that the use of a probabilistic sub-CA model provides a solution for the decentralised approach to observability and estimation of the deterministic sub-CA. However, the probabilistic CA model raises new issues such as the new definitions of observability and reconstructibility. We have not been able to go further in the study of probabilistic sub-CA, mainly due to lack of time, but we have the intuition that they could be very useful for the observation of two-dimensional non-linear CA.

CONCLUSION

In this third chapter, we have given different criteria to evaluate the notions of observability, reconstructibility and adaptability proposed in the previous chapter. In the first section, we focused on ACA and in the next two other sections we studied non-linear CA.

The use of ACA provides a way to assess the injectivity of the output sequence using linear algebra. The observability criterion is then a transposition of the Kalman criterion from classical control theory. The adaptability and reconstructibility criteria are verified using the kernel of the associated operators. The use of ACA provides criteria with polynomial algorithmic complexities that allow the evaluation of these criteria with a large number of cells. However, ACA represent only a very small part of all possible CA. Therefore, the case of non-linear CA is discussed in the second part of this chapter.

In this second part, we first made the link between BN and CA. This allowed us to transpose the results concerning the observability and reconstructibility of BN to CA. We then proposed a different approach that takes advantage of the regularity of the lattice to propose better observability and reconstructibility criteria. These criteria can be used on any CA derived from definition 2.1, but the exponential algorithmic complexity makes it difficult to use for CA with more than a dozen cells.

In the last part, we proposed a method for the decentralisation of observability analysis. This method split the observability and reconstructibility problems in order to reduce the algorithmic complexity. The decentralisation works well only for one-dimensional CA. For two-dimensional CA, we suggested an approach using a probabilistic CA for the state estimator. This should reduce the number of sensors in each sub-CA that are used to measure the boundary cells state values.

Concerning section 2.2.3, the main contributions of this chapter are the use of the Kalman criterion for CA and the definition of the reconstructibility and adaptability criteria for ACA. For non-linear CA, the contribution of the thesis lies in the transposition of the observability and reconstructibility criteria from BN to CA. The relational approach and the decentralisation of observability are also two major contributions of the thesis as they easily reduce the algorithmic complexity in particular cases. All these results have been published in (Plénet et al., 2022b) (currently in press) for ACA and in (Plénet et al., 2022a) for non-linear CA.

In chapter 4 we will study observation through the synchronisation of CA. The approach used will be different from the one used here. The synchronisation will be used as a state estimator without checking the reconstructibility, as we did in section 3.3.3. The performance of the state estimator will be studied statistically through a large number of simulations. chapter 5 will provide illustrations of observation analysis and estimation developed in this chapter, on large and physically-motivated examples: a simplistic forest fire propagation model, a road traffic model inspired by R184 and a high quality random number generator. These examples will be used to apply the different criteria presented throughout this chapter, but also to compare them with the results of chapter 4.

INTRODUCTION

In the previous chapter, we defined observability and reconstructibility criteria for additive, affine and non-linear CA. These two notions guarantee that the state of the system can be deduced from the measurements made by the sensors. In section 3.3.3 we described a state estimator which makes it possible to determine the state of the system while it is being measured. It depends on the verification of the reconstructibility criterion that is a necessary condition to ensure the good convergence of the state estimator. However, the algorithmic complexity makes it difficult to use these tools for CA with a large number of cells. In this chapter we present a different method. We first define a state estimator and then, we evaluate its observation "quality" statistically from a large number of simulations. For this purpose, we will use the CA synchronisation as a state estimator.

CA synchronisation is a direct application of the synchronisation of physical systems. It is a concept that has been studied for many centuries and has recently been adapted for CA. The study of the synchronisation of two systems consists of pairing two distinct physical systems by some kind of coupling and study whether their states become identical or not. The most famous example of synchronisation was discovered by Christian Huygens in 1965 when he found that two unsynchronised pendulums (i.e. with an arbitrary phase) placed on the same surface would eventually synchronise (in phase opposition for Huygens's discovery but more recently studies by Fradkov and Andrievsky (2007) have shown that in-phase synchronisation can exist).

When we study the synchronisation of CA, there are two identical CA with different initial configurations. The coupling between the two CA is achieved by coupling some cells from the "driver" to the "replica". This is called unidirectional coupling. When a cell is coupled, the state of this cell on the driver is copied to the same cell on the replica. The synchronisation between the two CA varies according to the nature of the coupling and the methods used. [START_REF] Dogaru | Binary chaos synchronization in elementary cellular automata[END_REF] studies the synchronisation of chaotic ECA using a single coupling cell and characterises the synchronisation according to the number of cells and the ECA rule. [START_REF] Urıas | Synchronization of cellular automaton pairs[END_REF] studies the synchronisation of linear ECA with several coupling cells and characterises the position of the coupling cells to ensure full synchronisation of the replica on the driver. This approach is similar to the one we presented in section 3.2 when studying ACA. On the contrary, [START_REF] Bagnoli | Synchronization and control of cellular automata[END_REF] study synchronisation of one-dimensional CA (mainly ECA and totalistic CA) using a coupling probability which represents the probability of a cell of the CA to be a coupling cell. The results are not characterisations of the synchronisation but rather statistical results that identify the critical probability for synchronisation to be achieved. This critical probability can also be approximated using the CA Lyapunov exponent [START_REF] Bagnoli | Synchronization and maximum lyapunov exponents of cellular automata[END_REF].

In this chapter we will start with a general presentation of CA synchronisation by presenting the different properties of synchronisation. Then, we will present how synchronisation can be used as a state estimator and its link with the state estimators of classical control theory. Finally, we will introduce a sensor placement method to improve synchronisation performance for CA with small initial error. We will compare the two synchronisation methods for the observation of ECA.

GENERALITIES ON THE SYNCHRONISATION OF CELLULAR AUTOMATA

Throughout this chapter, we will focus on the synchronisation proposed by [START_REF] Bagnoli | Synchronization and control of cellular automata[END_REF] as it combines the use of a mobile sensor network, non-linear CA and also (and most importantly) a statistical study of the synchronisation performance. This leads to a low algorithmic complexity compared to the evaluation of observation performance. In [START_REF] Bagnoli | Synchronization and control of cellular automata[END_REF], the synchronisation of the replica with the driver is achieved through copying the state of some cells (called coupled cells) of the driver in the matching cells of the replica. The coupled cells can change at each time step, which allows the representation of mobile sensors.

Presentation of the Synchronisation

The objective of this chapter is to introduce CA synchronisation as a state estimator and to evaluate its observational performance. We present this in more detail in the next section. In order to remain consistent throughout the chapter, we use, from now on, the notations of the state estimator, i.e. for the state of the system (the driver) and ˆ for the estimate (the replica). Similarly, the coupling cells between the driver and the replica represent the cells measured by the sensors, thus the set of coupled cells is the set of measured cells L . Consequently, the ˆ state of the replica can be expressed as :

ˆ ( ) = ( ) if ∈ L ˆ ( ) else (4.1)
Before giving the state representation of synchronisation, we shall start with some reformulations of the notions defined in chapter 2. To model the coupling between the two CA, we use a vector representation for the configurations that can easily separate the cells that are coupled and those that are not. To achieve this, we use the vector representation that we have already used in section 2.2.3 for the definition of ACA and in section 3.2 for the study of the observability and reconstructibility of ACA. This representation provides a vector representation of the configuration where the states of each ( ) cell is arranged as a vector = ( 1 )

( 2 ) • • • ( ) . Secondly, as we will not be using synchronisation only for ACA then the global transition function is not necessarily an affine map, hence we shall keep using the notation +1 = ( ) for the evolution of the CA.

The coupling between two CA is done by copying the state of the cells from the driver to the replica. In this case the sensor network strictly respects the definition 2.4 and the output operator is additive and can be expressed with the matrix . However, we will not use the matrix to represent the coupled cells but the diagonal matrix = . The diagonal matrix indicates which cells are coupled, the value 1 indicates that the corresponding cells are coupled. Consequently, selects only the coupled cells of whereasselects the cells that are not coupled. Finally, the state representation of the synchronisation is expressed as : Definition 4.1 (Bagnoli et al. Synchronisation). Let A be a CA and its global transition function. Let H be a time-dependent sensor network associated to the matrix . The synchronisation of the replica ˆ over the driver is done by the following:

+1 = ( ) ˆ +1 = ( -) • ( ˆ ) + • ( ) (4.2)
In [START_REF] Bagnoli | Synchronization and control of cellular automata[END_REF], the coupled cells are chosen randomly at each iteration from a coupling probability . Different coupling methods exist and are presented in section 4.3. We will study their synchronisation performance in relation to the state estimation problem.

To investigate the synchronisation, we use the synchronisation error defined by eq. ( 4.3). By doing so, we can represent the difference between the replica and the driver independently of the states of the replica and the driver. The system is considered to be synchronised when ˆ = but it is possible to provide more accurate information by considering the cells that are synchronised ˆ = . To do this we define the normalised synchronisation error in definition 4.2 which represents the percentage of cells that are not synchronised at time .

Definition 4.2 (Normalised Synchronisation Error

). The percentage of unsynchronised cells within the replica is called the normalised synchronisation error and is express by:

= 1 ∈L 1 - ( ) (4.4)
where ( ) represents the Kronecker delta of ( ) , it is equal to 1 if ( ) = 1 and 0 otherwise.

For the example of ECA synchronisation in Figure 4.1, we have chosen arbitrarily coupling probability = 0.2 and we notice that the replica took about 110 iterations to synchronise to the driver (see Figure 4.2). For the chosen ECA, a coupling probability of 20% represents a total of about 20 coupled cells per iteration. However, we have seen in the previous chapter that not only the position of the sensor is important but also the number of sensors (see example 3.2). Similar concerns can be raised for the synchronisation of the CA. What is the impact of the coupling probability on the synchronisation? Is there a minimal coupling probability that ensures synchronisation?

In order to answer these questions, we shall explore some examples of synchronisation with different coupling probabilities. On Figure 4.3, we can make two hypotheses: First impacts the synchronisation of the replica (for = 0.1 and = 0.2 the replica does not synchronise and the bigger is, the faster it synchronises); second, impacts the normalised synchronisation error decrease (the bigger is, the fewer black cells at time ). The influence of the coupling probability (number of sensors) on the speed of convergence seems to be consistent with the results of the observation, and in particular with the lower bound of the Cayley-Hamilton Theorem which decreases with the number of sensors. Moreover, after conducting several simulations (not presented here), it seems that the replica never synchronises for = 0.1 and always synchronises for = 0.3 and = 0.4. The case of = 0.2 is more peculiar since the replica synchronises in about one fifth of the simulations in this case. In order to analyse more precisely the impact of the coupling probability on the synchronisation error, we performed a large number of simulations and calculated the mean normalised synchronisation error. This value is represented by the continuous curve in Figure 4.4. Considering the particular case of = 0.2, we notice that = 0.08. However, as there are some cases where the replica is fully synchronised (i.e. = 0), there is a lack of information to deduce the impact of on the normalised synchronisation error (apart from the complete synchronisation of the replica). For this purpose, we represent the synchronisation rate, i.e. the total synchronisation rate of the replica over all simulations, by the dashed curve. Thus we notice that the first cases of total synchronisation appear around = 0.15 and the synchronisation rate continues to grow to reach 100% around = 0.31. This confirms our first hypothesis on the direct impact of the coupling probability on the total synchronisation of the replica on the driver. Moreover, by comparing the synchronisation rate with the normalised synchronisation error for probabilities lower than = 0.15, we observe a decrease in the normalised synchronisation error without an increase in the synchronisation rate. For = 0.05, about 40% of the cells are not synchronised while only 22% of the cells are not synchronised for = 0.15. Adding coupling cells brings more information than just the value of the cell itself. We can finally conclude that an increase in the probability decreases the normalised synchronisation error independently of the synchronisation rate confirming our second hypothesis.

In this section we have presented synchronisation and more precisely the synchronisation model of [START_REF] Bagnoli | Synchronization and control of cellular automata[END_REF]. This model is designed to synchronise a replica to a driver by using randomly chosen coupling cells. We have studied an example of synchronisation for the ECA R110-100-NB for which we have been able to estimate the critical coupling probability ≈ 0.31 which permits a perfect synchronisation of the replica on the driver. This perfect synchronisation of the replica on the driver makes it possible to use synchronisation as an observation tool. The state estimator would be the replica that we seek to synchronise with the system in order to determine its state. It is precisely this application of synchronisation that we shall study in the following section.

SYNCHRONISATION AS STATE ESTIMATOR

In this section, we present the use of synchronisation as a state estimator. We will start by presenting the connection with state estimation in classical control theory. We will also present how coupling cells can be seen as sensors and how the type of sensor directly impacts the synchronisation performance. We will conclude by presenting some ideas for improving the state estimator for a particular system by using a certain type of sensor or by modifying the state estimator model.

In the case of so-called classical synchronisation, there is not much of a bridge between synchronisation and state estimation because the coupling between the two systems is bidirectional. The state estimator is not supposed to influence the system it observes. In the case of CA synchronisation, it is precisely this unidirectionality of the coupling that makes the link with state estimation possible. Indeed, the state estimator constructs an estimate of the state of the system from measurements made on it, and the estimate is considered "perfect" when the state of the system and the estimator are equal (or at least close enough). We directly relate the state estimator to the replica, the system to the driver and the sensors to the coupling cells.

Moreover, the synchronisation equation ( 4.2) is similar to the state estimator of linear systems presented in [START_REF] Kalman | On the general theory of control systems[END_REF]. Indeed, we can compare the expression of the replica of an ACA (4.5) with the expression of the state estimator of LTI systems (4.6). We notice a similar expression where the coupling matrix represents the product ( is the gain matrix which guarantees the convergence of the state estimator) with the difference that the measurements are taken at time + 1 for the synchronisation and at time for the state estimation.

Synchronisation: ˆ +1 = ( -) • ( ˆ ) + • ( ) = ˆ + ( +1 -ˆ +1 ) (4.5) State Estimator: ˆ +1 = ˆ + ( -ˆ ) (4.6)
Remark 4.1. The gain matrix is usually computed using a pole placement method (Ackermann, 1972) or a constrained optimisation synthesis [START_REF] Kalman | On the general theory of control systems[END_REF]. These methods could, under the requirement of a proof, be applied to ACA in order to create a state observer for ACA.

As mentioned, the coupling cells represent the sensors of the system. The synchronisation model of [START_REF] Bagnoli | Synchronization and control of cellular automata[END_REF] takes into account a time-dependent coupling matrix and therefore can handle mobile sensors. However, what is the coupling probability in case of mobile sensors? One can consider that if the cells are randomly observed then it can be considered that they are mobile sensors whose speed of movement is largely superior to the dynamics of the system (sensors can move anywhere in the lattice at each time). This may also be the situation of a sensor network where only certain sensors are active (as presented in eq. (2.21)). In Figure 4.5, we represented the normalised synchronisation error for random sensors but also for fixed and mobile sensors. The initial position of the sensors is determined randomly in a similar way to the random sensors. In mobile sensor network, their initial position is determined randomly and each sensor moves one cell to the right (as in example 3.1). A notable difference between these three methods is immediately apparent in terms of synchronisation performance. The mobile sensor network performs better than the random sensor network, which itself performs better than the fixed sensor network. These results are, however, very specific to the rule studied. Indeed, if we consider the ECA R184-100-PB, which is an example of the road traffic model (see Figure 2.5 and section 5.3), the synchronisation performances represented on Figure 4.6 are quite different. Indeed, in this model the "cars" (cell with state 1) move one cell to the right at each time step. It is therefore impossible for the mobile sensor moving at the same speed to measure the car if it is not on the same cell as the sensor. On the contrary, for the fixed sensor network, as the car is moving on the lattice, it will, sooner or later, be measured and therefore synchronised. Finally, in order to be the least sensitive to this kind of detail during the general studies, we shall stick to random synchronisation. This also allows us to apply the different results of the synchronisation. However, when we apply state estimation with synchronisation in the context of physical system observation (see chapter 5), we will compare in more detail the sensor network topologies as well as the impact of the different coordination methods on the synchronisation performance.

For some applications, in addition to the sensor placement method, the replica model can also be adapted to improve synchronisation performance. The replica model will differ from the driver, which may permit to the replica to converge faster to the driver. In the forest fire example (see section 5.2), the fire spread model is slightly modified. In the initial model, it is the fire that propagates in the forest, but in the "improved" model, the ashes also propagate. Therefore, when a sensor measures ash, it indicates that a fire was present on that cell some time ago, so the neighbouring cells have also burnt and are now ash. This has the effect that the measurement of a cell with ashes is useful for synchronisation when initially it would not have contributed to reducing the synchronisation error (beyond its own value).

In this section we have seen how the replica of the CA synchronisation can be used as a state estimator. The coupling cells can be considered as sensors. We also observed that sensor density has an influence on the normalised synchronisation error. The sensor network coordination method has an influence on the critical density that guarantees the full synchronisation of the replica. In the following section, we investigate the particular case of a small initial synchronisation error (a few cells of error). The objective will be to model the propagation of the initial error in order to improve the synchronisation algorithm.

STATE ESTIMATION OPTIMISATION FOR SMALL INITIAL ERROR

In this section, we will consider synchronisation when the initial error is small. Indeed, as we stated in the previous chapter, it is likely that for some applications there are constraints on the plausible initial configurations. In this case, the initial synchronisation error is limited. To borrow from the example of the propagation of a forest fire, if the topology of the forest is known and only one cell can be ignited at initialisation, thus there is only one error cell. The synchronisation error is then very small. We will therefore study how this initial error propagates in order to develop an optimised synchronisation method for monitoring systems with a low initial error.

Impact of the Initial Error on the Synchronisation Error

In order to study if and how the initial synchronisation error impacts the evolution of the normalised synchronisation error, we show in Figure 4.7 the normalised synchronisation error as a function of time for different initial error 0 values. These results were obtained through several synchronisation of the ECA R18-100-PB and coupling probability = 0.1. The initial configuration 0 was randomly initialised and and ˆ 0 was initialised to the value of the driver with some erroneous cells (1 cell for 0 = 1%, 2 cells for 0 = 2% and son on). The initial synchronisation error 0 has a clear impact on the overall normalised synchronisation error. Its first influence is on the speed of convergence towards the asymptote. Indeed, the 10% curve seems to converge faster than the 20% and 50% curves which converge earlier than the 1% and 2% curves. The second effect of the initial error is on the value of the asymptote when 0 is small enough. For 10%, 25% and 50%, converge towards the same asymptote value, around 0.23. However if 0 is sufficiently small, the reached asymptote is lower than this "generic" one. To understand the difference between the two asymptotes, we studied the evolution of the error as a function of time for the particular case of a single cell of initial error ( 0 = 1%). As we can see on Figure 4.8, there are two very different kind of evolution of the synchronisation error . On one hand, in Figure 4.8a, the error spreads until it covers the whole CA and reaches the asymptotic non-zero value. On the other hand, in the very specific case depicted on Figure 4.8b, the replica synchronise with the driver and the normalised synchronisation error reaches zero. Therefore, when we average these two cases, which we did for Figure 4.7, we obtain a lower asymptotic value. For the remaining of the study, we chose to dissociate the two cases and to not consider the total synchronisation cases when we study the asymptotic value. To characterise the impact of the initial error on the performance of the synchronisation, we only consider the cases of total synchronisation which do not influence the average value. Figure 4.9 represents this asymptotic value as a function of the initial error. First, if we consider only the asymptotic synchronisation (without special cases of early complete synchronisation), the value of the asymptote does not depend on the initial error. Second, the value from which the average error with and without total synchronisation become different depends on the coupling probability : the stronger, the greater the chance of total synchronisation.

Modelling of the Error Spreading Dynamics

In order to explain the dynamics of the evolution of the synchronisation error, we study how the error propagates within the CA as a function of the coupling probability. To do so, we start by studying the propagation of the error within the simple case of a single erroneous cell and then, we generalise these results to two or more cells. To study the propagation of the synchronisation error, we shall study the propagation of a single ECA and generalise the results to all ECA. To decide which rule we shall study, we have reported the synchronisation error with null coupling probability in Figure 4.10 as a function of the class of the ECA. Class 1 shows no interest as regardless of the initial configuration, the state of all cells becomes rapidly uniform. Class 2 is also not very interesting because the error does not propagate over the whole lattice. Class 4 seems to be more interesting. However the propagation structure varies strongly depending on the initial configuration. Finally, we will be interested in class 3 but not in the R30 rule because it is not symmetrical. We eventually choose the R18 ECA because it is the smallest symmetrical class 3 ECA. Comparing the different error propagation for the ECA R18 in Figure 4.11, we adopted a triangle as a simple geometric model for these dynamics. Therefore, to describe how the synchronisation error spreads, two parameters will be used: the first being the aperture angle of the propagation triangle, and the second being the shift angle between the altitude and the median of the triangle. Indeed, the median of the triangle seems to vary from one simulation to another. Figure 4.12 describes the geometry associated with these angles and which describe respectively the aperture angle and the shift angle. From Figure 4.11, it appears that for R18 the aperture angle of the triangle is inversely proportional to the coupling probability and the shift angle is null. For the sake of simplicity, we will not use directly the and angles but their tangents, which represents spread velocities (the opposite side is the altitude which is the time here). We will simply call and the velocities associated to the angles and not the angles themselves. Therefore, the error spreading ratio represents the mean number of cells by which the triangle base increases at each time step and error shift ratio the mean number of cell shift at each time step. By default, a positive error shift ratio reflects a shift to the right and a negative error shift ratio a shift to the left. As this is the synchronisation of ECA, the error can only propagate, at each time step, a maximum of one cell to the right and one cell to the left. Thus, the coefficient cannot exceed 2 and the coefficient cannot exceed 1. The case where = 1 can only happen if = 0 because the middle of the base of the triangle is shifting less quickly than its edges (found for example with R184).

Based on Figure 4.12, we can express the width and the middle 1 of the error at time by 1 = 0 + • and = • . The width must also be restricted by the size of the lattice . Subsequently, from the width of the error , we are able to deduce the normalised synchronisation error from the asymptotic value of the error and the proportion of the lattice that is covered by the error / . The value of the asymptotic synchronisation error is the value of when the timing error is present over the entire lattice. The average value of the asymptote is given in Figure 4.9 for three values of . We finally propose the following corollary which gives the expression of .

Corollary 4.1. The normalised synchronisation error can be estimated from the parameter as well as the value of the asymptote associated to the coupling probability . Thus, the normalised synchronisation error is defined by : =

• min( ; • )

We can calculate the mean value of the error spreading ratio by measuring the area of the error at time and divide by current time to obtain the tangent of . Figure 4.13 describes the evolution of the average spread ratio as a function of the coupling probability. For the first part, up to = 0.2, it is similar to an affine function of which we experimentally obtained the equation = -8.41 • + 1.95 using linear regression. This expression of the error spread ratio supports the hypothesis raised by Figure 4.8 which claims that is inversely proportional to the coupling probability. As specified in the previous section, we are not interested in cases where synchronisation is total because the propagation of error is zero. However, as we get closer to the critical coupling probability = 0.3, the number of total synchronisation increases significantly. The average is therefore no longer made on several thousand simulations but only a few hundred, which implies that the precision of the results decreases as we get closer to the critical coupling probability. Error Spread Ratio F . . The error spread ratio as a function of coupling probability for the ECA R 8--NB. The continuous curve is obtained by taking the mean of over 10 4 simulations. The dashed curve is the curve obtained by linear regression.

In Figure 4.13, we have plotted the mean values of alpha as a function of , but for a given value of , the coefficients are normally distributed. The same observation can be made for the error displacement coefficient . In order to have a better representation of and , we can calculate their mean and standard deviation as a function of the coupling probability as we have done for the mean value of in Figure 4.13. They are shown in Figure 4.14. However, as in Figure 4.13, the number of total synchronisations sharply increases as we approach the critical probability so that the statistics are made with fewer non-zero values.

Using the corollary 4.1, we are going to make an example for = 0.1. For this coupling probability, the error spread ratio follows a normal distribution with mean 1.124 and standard deviation 0.136, the asymptotic synchronisation error value taken from Figure 4.9 is approximately = 0.221. From the same figure, we can compute , the rate of total synchronisation among all simulation, whose value is = 0.305 for = 0.1. It must also be taken into account in order to represent the normalised synchronisation error of Figure 4.7. On Figure 4.15, the mean normalised synchronisation error computed through simulations is displayed as well as the estimated error with an fixed at the mean and an that follows the normal distribution. We notice that the use of the normal distribution in the calculation of the error explains the rounded curve when the error approaches the asymptote. However, the two theoretical curves have a difference with the real curve which is explained by a faster increase of the error during the first iterations which is caused by a higher as the error is not yet detected by the sensor, and therefore unsynchronised.

This method allows us to simply represent the propagation of the error in the case where a single cell is erroneous in the initial configuration. If we consider two or more erroneous cells then the modelling becomes more complex. Indeed, the multiple initial errors propagate independently until they collide; as shown in Figure 4.16. Thus, we must consider that the errors merge in a single (larger) source of error. Considering that the collision takes place at time 1 , we can consider that the error spread ratio for two initial erroneous cells is expressed as: The time 1 of the collision depends on the initial distance between the two initial errors, whose probability distribution depends on the boundary conditions used. Indeed, if we consider that the two erroneous cells are at the two extremities of the lattice, then the distance between the two is either 0 for periodic boundaries or for the other boundary conditions. Therefore, 1 can be expressed as :

( ) = 0 + 1 , if ≤ 1 ( 0 -0 + 1 + 1 ) 2 , if ≥ 1 (4.
0 • + 1 2 • 1 = 1 ⇐⇒ 0 + 1 2 • 1 = 0 + ( 1 -0 ) • 1 ⇐⇒ 1 = 0 0 -1 + 0 + 1 2 (4.8)
Moreover, since each of these initial errors is subject to the total and fast synchronisation (of probability ), the model must include, with probability 2 (1 -), a propagation with only one initial error using the model of Figure 4.12. With more than two erroneous cells, the operation is the same but it is necessary to take into account several collisions occurring at different times as well as the different scenarios of fast and total synchronisation. Using the different parameters , , , and used for Figure 4.15, we can do the same thing for two initial error cells. Figure 4.17 shows the three curves: that of the simulations, the constant theoretical value and the values following normal distributions. In this section, we first confirm the proportionality between the error propagation speed and the coupling probability. This makes it possible to model the propagation of the synchronisation error for one or two erroneous cells at initialisation. This model could be extended to more erroneous cells, but it becomes more complicated to model beyond several cells. In the next section, we will use this error propagation model to propose a more efficient sensor placement in the case of a single erroneous cell.

Optimisation of Algorithm for a Single Erroneous Cell

In this section we propose a method for coordinating sensors for synchronisation where the initial synchronisation error is small. The objective is to identify the cells in the replica lattice that may be in error and then concentrate the sensors in these areas to increase the chances that the error is measured and synchronised. We will first present the construction of the possible error area and then adapt the synchronisation of definition 4.1 using this possible error area and compare the performance of the two methods.

In order to identify the error area, the sensor network must first measure an error. From the position of this error cell, the synchronisation error propagation model can be used to find the possible positions of the original error cell. Let us note ˆ 0 the initial error zone which corresponds to the set of cells that can lead to errors measured at time . Then, by using the model of the propagation of the synchronisation error, it is possible to find ˆ , the set of cells which can be erroneous at time by considering ˆ 0 the initial error zone. Figure 4.18 shows the geometric construction of the ˆ 0 error zone with a backpropagation of the error measured by the sensor array as well as the ˆ error zone at time . The error spread ratio corresponds to a ratio large enough to include all (or a large part) of the possible error spread ratios at the given coupling probability. As follows a normal distribution, a ratio = + 3 encompasses 99.7% of the possible spreading ratios. However, as we have seen in Figure 4.15, the error spread ratio is larger at the beginning since the error is still too low to be synchronised. We must then consider the maximum ratio for this case, i.e. max = 2.

F

. 8. Schematic of the backpropagation of the synchronisation error to find the initial error area ˆ 0

In a formal sense, we define the initial error zone ˆ 0 corresponding to the erroneous cell at time as:

Ξ , : ↦ → ˆ 0 = { ∈ L| | -| ≤ • 2 } (4.9)
Similarly, we define the error zone ˆ at time from ˆ 0 by :

Φ , : ˆ 0 ↦ → ˆ = { ∈ L| ∃ ∈ ˆ 0 , | -| ≤ • 2 } (4.10)
As new errors are detected by the sensor network, we can adapt the initial error zone. Indeed, as we know that there is only one erroneous initial cell, we know that this cell is in every ˆ 0 . Therefore the initial error area can be refined using the intersection of all the initial error areas of all the errors detected by the sensors. In this way, it is possible to reduce the size of the error zone at time but also to locate the position of the initial error. We can express the evolution of this by ˆ ( ) 0 (4.11) where Y represents the set of erroneous cells measured by the sensor network at time .

ˆ ( +1) 0 = ˆ ( ) 0 ∩ ∈Y Ξ , ( ) ˆ = Φ , ( ˆ ( ) 0 ) (4.11)
Now that the error area can be estimated, it remains to position the sensors. The method consists in placing the sensors only in the area where the error could be present. The sensors are still placed randomly based on the coupling probability. As the area of observation is reduced, we can increase the probability of coupling in proportion to the reduction of the area of observation. Thus, the density over the whole lattice remains the same but the density over the error area increases. This new method will result in a lower critical coupling probability as shown in Figure 4.19. The coupling probability in the error area ˆ is described by: As shown in Figure 4.19, the optimised synchronisation performs better than the usual one with a critical control strength at 0.05 instead of 0.21. However, when the control is too weak, the difference between the two is negligible because the first error cell is detected too late by the sensors. The error area ˆ is too large and therefore the optimised coupling probability is not sufficient to synchronise the replica on the driver.

= • | ˆ |
In Figure 4.20, we have compared the optimised synchronisation to the regular one for the ECA belonging to different classes presented in Figure 4.10. The results obtained by using the maximum error spread ratio used for the backpropagation = 2. In the three examples, the optimised synchronisation performs better than the regular one. R172-500-PB, and more generally Class 2 ECA, exhibit a lower critical coupling probability due to the fact that the error does not spread on the whole lattice and remains constant after a few iterations. Because the error is only located on certain cells of the CA, the synchronisation time directly affects the synchronisation performance. Indeed, if it is synchronised for a sufficiently long time, then all the error cells have been coupled and therefore synchronised in a random manner. In this case, the synchronisation performance depends strongly on the synchronisation time horizon and less on the synchronisation method (classical or optimised synchronisation). Therefore, using the optimised synchronisation results in a lower (or even insignificant) performance gain than for the other examples. The use of optimised synchronisation with R30-500-PB does reduce the normalised synchronisation error, but not the critical coupling probability. This is due to the fact that the use of optimised synchronisation allows the replica to be synchronised in a large number of cases, but it is necessary to reach the critical coupling probability ≈ 0.3 in order for the complete synchronisation to occur. The average is therefore lower but, as in Figure 4.7, it is an average between synchronised cases and unsynchronised cases at the asymptote. The presented sensor placement method only works for one error cell. If the second error cell is not in ˆ 0 after the first measurement, then no sensor will be able to measure that error because the probability outside the error area is 0. It is therefore necessary to consider two initial error zones ˆ (1) 0 and ˆ (2) 0 for the two error cells. If the sensors measure an error cell that does not correspond to one, it is the other. Thus, if the errors are sufficiently distant at the beginning then it is possible to have two disjoint error zones. Otherwise it is more difficult to know which error triangle the measured error cell belongs to.

Several ideas could be put in place to deal with this case. For example, Plénet et al. (2020b) use sensors with different roles to monitor the propagation of forest fires. The fire model is represented by a CA but they do not use synchronisation, the replica does not have the same dynamics as the driver. In this example, some of the sensors called "followers" have the objective to measure the cells in the error zone while the others, called "explorers", measure the outside of the zone in order to detect new ignitions. In the case of CA synchronisation, in the error zones, the trackers have a sufficiently high coupling probability to guarantee synchronisation and outside the zone the explorers have a lower probability but sufficient to "detect" new errors.

CONCLUSION

In this chapter we have studied the synchronisation of cellular automata. We have first seen how it can be used as a state estimator and especially that its definition is very close to the state estimators of classical control theory. Next, we studied the synchronisation for the particular case where the initial synchronisation error is very small. We were able to model the propagation of this initial error using basic geometry in the case of one or two error cells. We ended this chapter by proposing a sensor placement method that uses this model to determine the error area. This method of sensor placement is more efficient than the usual synchronisation and in some cases allows a lower critical coupling probability to be obtained.

Finally, synchronisation appears to be a good alternative to the notions of observability and reconstructibility when the studied CA have a large number of cells. However, the study of the performances provides a statistical estimation of the observation performances but does not guarantee, as opposed to the reconstructibility, the correct observation of the system. In the next chapter, we shall illustrate synchronisation, observability and reconstructibility on practical examples and will be able to compare in detail the synchronisation with the approaches proposed in chapter 3.

CHAPTER 5

Application to Monitoring of Complex Systems

RÉSUMÉ

Dans ce dernier chapitre, nous allons appliquer les méthodes d'observation présentées dans les chapitres précédents sur trois exemples concrets. Pour le premier exemple, nous allons étudier un modèle de propagation de feu de forêt. Cet exemple permettra de détailler la méthode de construction d'un estimateur d'état en utilisant à la fois l'observabilité d'AC non linéaire et la synchronisation. Dans le second exemple, nous étudierons un modèle de trafic routier et plus particulièrement le problème de la reconstructibilité décentralisée permettant de construire un observateur d'état modulaire pour la surveillance des réseaux routiers. Nous terminerons avec un exemple d'AC générateur de nombres aléatoires. Nous utiliserons l'observabilité des AC affines pour trouver les nombres aléatoires générés par celui-ci.

INTRODUCTION

The main objective of this last chapter is to illustrate the observability assessment methods and tools presented so far by applying them to three very different examples. The aim is not to solve these systems' observation problems but to clarify our approach.

For the first example, we will study a forest fire propagation model. The objective will be to set up a method to detect and monitor the fire spread in an efficient way. To do this, we will first use a relatively simple fire spread model and compare it with a more complex model. We will then detail the method of constructing a state estimator using both non-linear CA observability and synchronisation. We will then conclude this example by comparing the advantages and drawbacks of both methods.

In the second example, we will study a road traffic model. We will first study its reconstructibility and then we will study the decentralised reconstructibility. We will finish by studying the reconstructibility of an intersection model with the objective of building a modular state estimator for larger road network monitoring.

For the last example, we will study a CA-based random number generator. We will use the observability of affine CA to find the series of random numbers generated by it from a small number of observations. We will show how observability can be used in a hardware attack.

DETECTION AND MONITORING OF FOREST FIRE SPREAD

In this first example, we will study a forest fire propagation model with the intention of providing forest fire detection and monitoring. We will start by choosing a fire propagation model that corresponds to the definition 2.1 for CA, that we made at the beginning of chapter 2. Then, we will present the different parameters that the model can take into account. Afterwards, we will study the observability, the reconstructibility, and the synchronisation of this model in order to build a state estimator. This example will serve for the comparison between the two different methods we have studied in this thesis.

Presentation of the fire propagation model

In the introduction to this thesis, we discussed two fire propagation models, the first proposed by [START_REF] Karafyllidis | A model for predicting forest fire spreading using cellular automata[END_REF] which uses the percentage of biomass consumed as a state and the second, a trivial fire propagation model which has discrete states to represent the fire. However, as we pointed out at the end of section 2.2.2, the cell state of the Karafyllidis and Thanailakis model is continuous and cannot be represented with the definition of cellular automata by El Yacoubi. Therefore, the results on observability and synchronisation can only be applied to the second model.

In this section, we first present the Karafyllidis and Thanailakis model by highlighting the different aspects it can model. Then, we will define, in relation to definition 2.1, the trivial fire propagation model and we will demonstrate that this trivial model can be used to model some of the propagation dynamics present in the Karafyllidis and Thanailakis model. Finally, we will present several properties of the trivial fire propagation model, such as percolation, which is essential to understand some results on observability and synchronisation.

Karafyllidis and Thanailakis Model

Karafyllidis and Thanailakis (1997) developed a CA model of forest fire propagation that is able to model the circular propagation of forest fire and to take into account some external factors such as the wind or the terrain elevation. The model makes use of a regular lattice of square cells where the cell state represents the percentage of biomass consumed by the fire. The state varies continuously between 0 and 1, where 0 represents an unburnt forest square and 1 a fully burnt one.

To spread the fire, the authors chose to define the consumed biomass at time as the sum of the consumed biomass of the neighbours, with factors that depend on different parameters presented in the next paragraph. This method is very similar to the one we use for Additive CA (ACA). However, the CA of Karafyllidis and Thanailakis is not an ACA due to the saturation of the cell state. Indeed, the consumed biomass is defined between 0 and 1; therefore the transition function uses saturation arithmetic between 0 and 1. Consequently, by considering the local transition function (2.8) and adding the saturation, we obtain the following local transition function where the represents the weight values for the neighbourhood cells:

+1 ( ) = min 1; =1 • ( ( ) ) (5.1)
In this CA, the Moore neighbourhood is used. When the coefficients for all the cells are equal, the fire propagation front has a square shape (see Figures 5.5a and 5.5b). To solve this problem and have a circular fire propagation front, the authors used a Moore neighbourhood with lower weights in the 4 corners. In this way, the neighbourhood offers an "octogonal" shape (see Figure 5.1a) because the corners are only covered at 83%. We denote this parameter which is equal to 0.83 if the cell is in the corner of the neighbourhood and 1 otherwise. The parameters related to the wind and the terrain topography are directly managed in the neighbourhood coefficients. For example, a north wind accelerates the propagation of the fire towards the south, on the neighbourhood. This is transcribed by a stronger coefficient on the cell located in the north than the other cells. Topography is modelled in the same way, higher grounds have higher coefficients. Figure 5.1b shows the coefficients and their position in the neighbourhood, represents the coefficient related to the topography on cell and represents the coefficient related to the wind on cell . As the topography varies with the position of the cell (this can also be the case for the wind), the coefficients of the neighbourhood change depending on the cell, so the CA is hybrid. The last parameter taken into account is the burning rate of the plant in the cell. In the same way as the topography, this changes according to the cell but applies uniformly to all the neighbours of the target cell. Karafyllidis and Thanailakis defined this value by = / , where is the burning speed / , is the burning time (s) and is the cell length (m). Finally, given the neighbourhood coefficient , , and , equation (5.1) can be written as :

+1 ( ) = min 1; ( ) + • 9 =2 • • • ( ( ) ) (5.
2)

The impact of these four parameters can be seen in Figure 5.2 where the fire fronts are represented in four different scenarios highlighting each of the parameters. While capturing some of the important parameters of fire propagation, the model proposed by [START_REF] Karafyllidis | A model for predicting forest fire spreading using cellular automata[END_REF] has some flaws. Several other authors have improved the model. Encinas et al. (2007a) have slightly modified the neighbourhood construction in order to provide a circular propagation of the forest fire. In (Encinas et al., 2007b), they also adapted the CA with a hexagonal cell mesh. [START_REF] Stephen | An improved cellular automaton model for simulating fire in a spatially heterogeneous savanna system[END_REF] added the moisture factor and validated it on a savannah fire in South Africa. Although there are many variants of this model, it is fundamentally a deterministic model which is not able to model certain factors such as new fire starts due to firebrands [START_REF] Holly A Perryman | A cellular automata model to link surface fires to firebrand lift-off and dispersal[END_REF].

In the next section, we will present a simple fire propagation model which respects definition 2.1 and for which we will study observability and synchronisation. We could have quantified the continuous states of this CA into different states, similarly to what is done in fuzzy logic, where the state ∈ S represents the percentage /( -1) of consumed biomass. However, this model would not have been as accurate as the Karafyllidis and Thanailakis model anyway. Instead, we chose to study a discrete and trivial model with only 4 states: empty, tree, burning tree and burnt tree. We will see that even if its formulation is trivial, it is still a model that can deal with different factors such as the circular propagation of the fire or wind, despite the fact that it has less granularity than the continuous model of Karafyllidis and Thanailakis.

Trivial Fire Propagation Model

What we will call the trivial fire propagation model is a discrete-state model where the cells can assume the following four states: empty, tree, burning tree, and burnt tree. The local transition function may vary from one application to another and from one type of model to another. Indeed, this model has already been studied many times, both as a deterministic model [START_REF] Alexandridis | Wildland fire spread modelling using cellular automata: evolution in large-scale spatially heterogeneous environments under fire suppression tactics[END_REF] and as a probabilistic one (Almeida and Macau, 2011). In our example, the transition function is deterministic and is represented by the diagram in Figure 5.3. A tree only catches fire when at least one of its neighbours (a discussion about the neighbourhood will follow further on) is on fire. In this case, the cell remains in the burning tree state for one iteration and becomes a burnt tree. The empty and burnt tree states are absorbing as well as the tree state as long as there is no fire.

In order to be able to apply the results we developed for observability and reconstructibility, we will formulate this CA according to definition 2.1. Therefore, we will consider a mesh of × square cells as well as a state space with the integer values 0, 1, 2, and 3 which correspond respectively to the state: empty, tree, burning tree and burnt tree. Formally, the parameters L, S and can then be formulated as :

• L = {0, 1, . . . , -1} × {0, 1, . . . , -1} lower density can be used for the Moore neighbourhood because the neighbourhood contains more cells. The choice for these density values are discussed in the next section when studying the percolation of the system. The density cannot be decreased below the percolation threshold because the fire would not propagate anymore. For the considered fire propagation model, we will use the Moore neighbourhood with the density of 0.5. As both neighbourhoods offer circular propagation, we prefer to use the Moore neighbourhood as it will allow a wider range of wind directions (see next paragraph). To model the impact of wind on fire propagation, [START_REF] Karafyllidis | A model for predicting forest fire spreading using cellular automata[END_REF] use different coefficient values for the neighbourhood cells. As already mentioned, this is impossible with the trivial model. Therefore, we will enlarge the neighbourhood in the wind direction and thus accelerate the propagation speed in one direction only. This method has already been studied by [START_REF] Trunfio | A new algorithm for simulating wildfire spread through cellular automata[END_REF] where the shape, size and direction of the neighbourhood is the main feature to model the progression of the forest fire. The new neighbourhood is constructed like the previous one with an additional cell depending on the wind direction. Figure 5.6a shows the position of this additional cell in the neighbourhood as a function of wind direction. Figures 5.6b and 5.6c show the progression of the fire with a northwest or east wind. The wind direction could change over time and space, but then the hybrid CA formulation presented in section 2.2.3 should be used.

With this model it is difficult to model the heterogeneity of the forest or the topography of the terrain. These two notions require a greater finesse in the speed of fire propagation. While remaining discrete, we have the possibility to deepen the model by lengthening the transient phase, i.e. the burning phase of the tree. This would provide the ability to model trees with different burning times . In their work, [START_REF] Schlotterbeck | Decentralized estimation of forest fire spread using mobile sensors[END_REF] is computed from the previous states ( -1 , -). This method does not add an extra state, but changes the formulation of the local transition function. For example, the condition of the fourth line of the transition function of the trivial model with a combustion period becomes :

if ( , ) = 3 or ∀ 0 ≤ < , -( , ) = 2 and -( , ) = 1
The trivial model we just presented provides a circular propagation of the fire while taking wind into consideration. Although there are several ways to improve the model, taking into account several parameters necessary for the good modelling of the propagation of a fire, it remains rather unconfigurable. Nevertheless, it will provide us with the opportunity to study the observability and synchronisation for a simplistic fire propagation model that captures some of the important properties of fire propagation. In sections 5.2.2 and 5.2.3, we will focus on windless propagation in a flat, homogeneous forest. In the next section, we will present two properties of this model related to percolation and Wolfram class.

Properties of the Model

In this part we will study the propagation properties of the fire in this CA and how it directly impacts the observation of it. We will start by studying the percolation, i.e. the way the fire propagates as a function of the forest density. Then we will discuss small and very large isolated forest areas and we will finish with a short study on the class of this CA in relation to the Wolfram classes defined in section 2.2.4. These different properties need to be studied before carrying out the study of observability, reconstructibility, and synchronisation as they provide essential elements to understand the behaviour of the system. Sensors must be correctly placed according to the dynamic of the system in order to efficiently measure the system.

Percolation initially refers to a fluid passing through a porous material. In our case, and more generally in complex systems, it is a question of finding out whether a disturbance in the system can spread throughout the system. For a forest fire, it is a matter of determining whether a fire in a given place can ignite the whole forest (or at least a very large part of it). The percolation is directly related to the density of the forest. If the density is too low, then the trees are too far apart and the fire does not spread. On the opposite, if the whole system is composed of trees, then the fire will have no difficulty in spreading over the whole lattice. To evaluate the percolation of the system, the forest is randomly initialised with a fixed density and one and only one tree is ignited. The fire spreads until there are no more fire cells,then we measure the burning tree rate, i.e. the percentage of trees that have burnt. Figure 5.7 shows the percolation for the trivial fire model with the two neighbourhoods: Moore and Von Neumann. The two curves, although having different values, are both sigmoid with similar slopes. They both have a very slow, almost stable, growth phase at the beginning and end. In between appears a phase transition of very fast growth. As Moore's neighbourhood is larger, the fire has an improved ability to spread (especially using the diagonals). This distinction between the two neighbourhoods explains the difference between the two curves. Earlier we mentioned specific density values to obtain a circular propagation. These values were chosen to get a burnt rate of 95%. This means that the vast majority of the forest burns, but some parts remain isolated and will only ignite when the fire starts in those parts. These isolated forest areas have a number of cells that are distributed exponentially with parameter ≈ 0.7. This means that more than half of these areas are composed of only one cell. The fact that there are isolated forest areas makes it more difficult to verify reconstructibility. Indeed, if these areas did not exist, the whole forest would be burnt whatever the starting point of the fire is. The final state for which the whole forest is burnt is the same for all initial conditions. Therefore the reconstructibility is trivial with one and only one final configuration. In this case, the objective of a finer reconstructibility analysis would be to ensure it as soon as possible, before the fire has spread to the whole system. Whatsoever, the existence of isolated zones avoids this particular case of trivial reconstructibility. Note that this does not impact in any way the study of observability, as we are then interested in the initial state, not the current one. The objective in this example is to monitor the spread of the fire. It is therefore necessary to reconstruct the state of the system before the forest has burnt down. In order to know the maximum time horizon for the study of observability and reconstructibility, we first need to estimate the average time of the fire propagation. Using the same simulation set as in Figure 5.7, i.e. a 100 × 100 cell lattice, with a density of = 0.5, we find that the mean burning time is 108 iterations with a standard deviation of 23 iterations.

Finally, with the previous results we can quickly deduce that the trivial CA we are studying is of class 2. That is, a CA that reaches a fixed or oscillating state (more details in section 2.2.4). Indeed, after a certain time, the system reaches a heterogeneous steady state where no cell is on fire anymore. However, the error may spread over the whole system before stabilising (if the density is high enough). In this case, the "filter" aspect of class 2 cannot be applied. As a result, the findings of the synchronisation on class 2 CA should be treated with caution as the error spread coefficient will not be as small as it should be. Additionally, there are two special cases (for densities = 0 and = 1) for which the state of all cells is the same at the end of the simulation. For these two cases, the CA is class 1.

In this section we have been able to study different properties that will directly impact the study of observability or synchronisation. The placement of the sensors will be a crucial element in order to measure all the "small" isolated forest areas. However, this CA has a relatively simple dynamic that seems to facilitate its study. In the next two sections we will build, or at least provide the tools to build, a forest fire monitoring system in order to know the state of the system as soon as possible, and especially before the forest has completely burnt down.

Observability

In this section we will study the observability and reconstructibility of the trivial CA model for the forest fire propagation. We will focus on a CA of size 100×100. In order to perform the study in a feasible time, we set conditions on the initial configurations that the system can take (as stated in section 3.3.2). At initialisation, there will be at most one cell that is in the burning tree state, all others will be either in the tree or empty state. We will also notice that ensuring the observability or reconstructibility of this system is not an easy task. That is why the objective of this example is not to deliver a sensor network capable of observing the forest, but only to demonstrate that the tools proposed in this thesis can be used for the monitoring of the propagation of a forest fire.

The study of observability and reconstructibility for this system is not easy. Indeed, the system is made up of several disconnected areas of forest, the largest of which contains on average 95% of the trees and the smallest, present in very large numbers, have only one or two cells. In order to verify observability and reconstructibility, it will be necessary to be able to determine in which zone the fire is located. To do this, sensors will have to be placed in each of these areas. Therefore, a large number of sensors will be needed, firstly to ensure the observability of the largest area, but also to ensure the observability in all the smaller areas.

The study of observability and reconstructibility will be carried out on a single forest topology. We choose the topology presented in Figure 5.8a which is a 100 × 100 cell lattice initialised with a density = 0.5. This forest generated has a total of 5054 trees distributed in a total of 50 distinct zones (see Figure 5.8b for more details on the sizes of these zones). In order to limit the number of operations (detailed in section 3.3.2) to evaluate observability, we will limit ourselves to the study of a single fire outbreak. At initialisation, there will be a maximum of one cell that is on fire. As a result, the observability and reconstructibility study will be carried out on 5055 initial configurations: 5054 configurations for all possible fire outbreaks and 1 configuration without any fire outbreak. As stated at the beginning of this section, we want to know the state of the system in order to monitor the spread of the fire. Thus, if the time horizon required for observability is too large, the state estimation is useless. In the previous section, we estimated the average time of the fire at 108 iterations for a density = 0.5.

We will choose a time horizon = 30, this choice is arbitrary and can be adapted according to the purpose of the monitoring. To perform the observability analysis, we need to choose first the sensor network. The choice of the position or trajectory for the sensors in the network remains an open problem (and not very well studied in the case of mobile sensors). The aim of this example is not to give a solution for forest fire monitoring, but to show that the methods presented in this thesis can be important tools for fire monitoring. In this sense, we will use a network of 150 static sensors placed randomly (see Figure 5.9a) on the trees in the forest (more details on the credibility of this type of sensor in remark 5.1). We will discuss possible sensor placement methods with more details towards the end of this section.

Remark 5.1. The choice of this kind of sensor is not necessarily irrelevant for forest fire monitoring. Indeed, the objective of these sensors is not to measure the 4 different states of the system but only the transient state of the fire. The only possible change of state is from tree to burnt tree through the state of burning tree. If the sensor detects fire, we know that all previous states were tree and that all subsequent states will be burnt tree. We can imagine that these sensors are similar to smoke detectors, and as soon as the sensor detects fire, it sends a message to the state estimator which takes into account the measurement. Thus, even if the sensor does not survive the fire, this will not impact the state estimation because once the burning tree state is measured all the following states are identical. This type of sensor can also be cost-effective compared to the use of satellite imagery or heat-resistant mobile sensors. Note that a non-reconstructible configuration is necessarily non-observable (see section . . ).

By evaluating the observability and reconstructibility with algorithm 1 for the sensor network and the time horizon = 30, we realise that out of the 5055 initial configurations 527 are non-observable and 117 are non-reconstructible. By representing the configurations by the position of the fire at the initialisation, we can represent on the lattice the position of the non-observable and non-reconstructible cases (see Figure 5.9b). Firstly, we immediately notice that all non-reconstructible configurations are located in small areas of the forest that do not have any sensors. This means that the large area of 4917 cells is reconstructible for a time horizon = 30. Then, the large concentration of non-observable configurations (especially in the right bottom corner) is justified by a low concentration of sensors in this area. A more efficient coverage of the sensors could have solved this problem.

The observability and reconstructibility evaluation for the 5055 configurations takes only a few dozens of seconds1 . Without any simplification on the initial conditions, the number of initial configurations to evaluate amounts to 4 10000 . Even knowing the topology of the forest and evaluating all possible cases (i.e. each nonempty forest elements can be either a tree, a burning tree, or a burnt tree), the number of configurations is far too high (3 5054 ) to be considered. For systems of this dimension, the use of simplification in the number of initial configurations is necessary to evaluate observability due to the exponential complexity. Now that we have evaluated the reconstructibility, we can implement the state estimator as presented in section 3.3.3. Hence, the initial state of the state estimator ˆ 0 will be composed of the 5055 initial configurations used for the observability and reconstructibility evaluation. In the case where a configuration is not reconstructible, then there will be no convergence to a single current configuration. However, as all non-reconstructible configurations are non-reconstructible because there are no sensors in those areas, this means that they will be mistaken for an absence of fire. As the isolated areas are small, the total error will be small. Then, to be able to compare with synchronisation later on, we will study the evolution of the error as a function of time for this estimator. The estimated state of each cell will be calculated from the majority of the state of that cell over all current configurations present in ˆ . For example, if for a given cell , 40% of the configurations in ˆ have the tree state for that cell ( ( ) = 1) and 50% have the burnt tree state ( ( ) = 3) and the rest have the burning tree state ( ( ) = 2), the estimated state of that cell will be burnt tree as it is the majority. In Figure 5.10, we have plotted the average error of the state estimator as a function of time. The error increases until = 5 and then starts to decrease until it reaches a fixed value at = 29. The starting time concerns the propagation of the fire before the sensors detect the fire, which is when the number of possible configurations is greatly reduced. The value at = 29 is not zero (but 29 = 2.9 -5 ) because of the 2.3% of non-reconstructible configurations.

To place the sensors correctly, it is not necessary to study the whole forest, but the individual areas. Indeed, as fire cannot spread from one area to another, each area can be considered as independent. Thus, the observability and reconstructibility of each zone can be ensured independently and, in the same way as for decentralised observability, the observability of the system is the combination of the observability of each zone. Therefore, at least one sensor per zone is required. However, one question arises as to the interest of such a method. Indeed, the objective is to monitor the propagation of the fire, but if the fire breaks out in a very small area, there will be no propagation over the entire forest. Therefore, the minimal area to be measured depends directly on the objective of the monitoring. Should any fire be detected in the forest? Should the spread of the fire be measured in order to fight it? At first glance, the placement of the sensors seems relatively simple. Indeed, by using randomly placed fixed sensors, we are able to ensure reconstructibility for a large majority of the lattice, 97.7% of the initial configuration are reconstructible. This is largely explained by the property of this class 2 CA for which three quarters of the states in S are absorbing states. If in our case, we wanted to ensure observability then we would have to spend more time on sensor placement. In that case, placing the sensors randomly or by trial and error would appear to be inefficient. We could use a heuristic sensor placement methods such as the Monte Carlo algorithm [START_REF] Chakraborty | A monte-carlo markov chain approach for coverage-area reliability of mobile wireless sensor networks with multistate nodes[END_REF][START_REF] Charles C Castello | Optimal sensor placement strategy for environmental monitoring using wireless sensor networks[END_REF], or evolutionary methods such as the genetic algorithm [START_REF] Liu | Optimal sensor placement for spatial lattice structure based on genetic algorithms[END_REF] where the objective is to minimise the number of unobservable or unreconstructible configurations. The management of mobile sensor networks is much more complex than for fixed sensors, because in addition to the initial position, the sensor trajectories must be carefully managed. Demetriou and Hussein are working on coordination methods for mobile sensors in the context of observation [START_REF] Michael | Estimation of spatially distributed processes using mobile spatially distributed sensor network[END_REF][START_REF] Michael | Guidance of mobile actuator-plus-sensor networks for improved control and estimation of distributed parameter systems[END_REF]. Decentralised methods of coordination could also be used, such as the multi-agent systems used by [START_REF] Schlotterbeck | Decentralized estimation of forest fire spread using mobile sensors[END_REF] for forest fire monitoring. In the latter, the observation method used is more related to synchronisation than to observability, but the observability criteria could be included in the behaviour of the agents.

In conclusion, in this section we have been able to study the observability and reconstructibility for the trivial fire propagation model. The reduction in the number of plausible initial configurations makes it possible to calculate observability and reconstructibility for a CA with several thousand cells. In this example, we did not try to place the sensors in such a way as to solve the problem of monitoring the spread of a forest fire. However, the simplicity of the model makes it possible for reconstructibility with a random placement of static sensors. In the next section, we will study synchronisation. The simulations will be done with the same number of sensors and on the same forest topology in order to be able to compare the performances of two observation methods.

Synchronisation

The objective of this section is to use the results of chapter 4 on CA synchronisation for monitoring the propagation of a forest fire. For this purpose, we shall use the same hypotheses as for the previous observability analysis, i.e. the forest topology is known and the fire can only start in one of the cells. We shall be able to compare the performances of the usual synchronisation and the optimised synchronisation for low initial errors. We will start by augmenting the trivial fire propagation model presented in Figure 5.3 to better fit the use of synchronisation as a state estimator.

Contrary to what we did in chapter 4, the replica and the driver will not be initialised randomly but with the forest topology presented in Figure 5.8. This will allow us to compare more easily the results of this section with those from the previous section. Thus, only the position of the fire outbreak will be randomly initialised (among the 5054 possible positions). For each simulation, we will use a sensor network consisting of 150 randomly initialised sensors. By default we will use random synchronisation but we will present the performances of different types of sensors thereafter. The results on the synchronisation will be studied statistically through the average of 10 4 simulations. In addition, as the empty cells state values cannot change, the normalised synchronisation error will be calculated with respect to the number of cells whose state can effectively change. Therefore, in the calculation of the normalised synchronisation error (4.4), will be taken as = 5054 instead of = 10000. The fire spread model shown in Figure 5.3 is a simple way to represent the spread of a forest fire. We have also seen that it allows to cope with different parameters by playing on the density of the forest and the shape of the neighbourhood. However, this model is not well adapted for synchronisation purpose because its absorbing states do not propagate. Indeed, if a coupled cell measures a cell with the burnt tree state, then this cell state will be copied to the same cell in the replica. As a burnt tree is measured, this means that fire was present on this cell not so long ago and that its neighbours are either burning or burnt. It is not possible for a burnt tree to be directly adjacent to a tree because we have not implemented fire extinguishment and there are no burnt tree cells in the initial configuration. However, with the current model, the burnt tree that was just measured will not impact the neighbouring cells of the replica even though we know that the neighbouring cells are necessarily burnt or burning. Therefore, we will augment the replica model so that a tree cell next to a burnt tree cell becomes a burnt tree cell, as shown in Figure 5.11. In Figure 5.12 we show the evolution of the normalised synchronisation error for both models. For each simulation, the sensors were positioned identically for both models. The normalised synchronisation error of the augmented model is significantly lower (i.e. 66% lower) than the error for the classical model. The error starts to decrease earlier in the augmented case (at = 10, compared to = 17 for the classical model) due to the propagation of the ash, so that the replica can start to synchronise as soon as burnt trees are measured. On the other hand, we notice that perfect synchronisation is not reached in the time horizon = 100 for any of the two models. The error for the augmented model is really low compared to the classical model ( 100 = 3.9 -5 for the augmented model and 100 = 6.0 -4 for the classical one). It is not until = 150 that the classical model reaches such a low error. Like in the previous section, it is necessary that all isolated areas are measured. In that sense, the augmented model does not provide a more efficient way to measure these isolated parts of the CA. However, measuring only one burnt or burning cell from these isolated parts is enough.

As we have seen in chapter 4 with Figure 4.5 and Figure 4.6, the type of sensor used for the coupling of the cells is of a great influence on the synchronisation performance. This difference also depends largely on the system we are studying. For this purpose, we will study in the case of the forest fire spread for 3 types of sensors: fixed sensors, mobile sensors and random sensors. We had already noted that the random sensors were mobile sensors with a speed largely higher than the dynamics of the system, therefore, we will study mobile sensors with relatively low speeds. We will study two sensor networks with mobile sensors. At each iteration, the sensors will move to a valid cell (i.e. not an empty cell) randomly chosen in its range of motion. For this study, we will use two mobile sensor networks, one with a speed of 1 and the other with a speed of 2. A speed of 1 corresponds to the speed of propagation of fire. To compare the performance, the four sensor networks will be initialised in the same way, the 150 sensors will have a random position which will be the same for the four sensor networks. Figure 5.13 shows the average synchronisation error for these 4 sensor networks with the classical model and the augmented model for the replica. For the classical model (see Figure 5.13a), the fixed sensor network performs best, both with respect to the time at which the error starts to decrease and to the error value at = 100. The other three sensor networks have approximately the same time for the error to decrease and the same final value. The difference between the mobile and the random sensors is the growth of the synchronisation error at the beginning which is 25% lower for the random sensors. With a high speed of movement, the random sensor network can scan the whole lattice and measure more cells, even if these cells are mostly trees and burnt trees. The performance of the fixed sensor network is explained by the non-displacement of the sensors. Indeed, when the front progresses on the lattice, the mobile sensors can skip a cell and measure ashes before measuring fire, this cannot happen with fixed sensors. They will never measure ash before measuring fire. This also explains why the performance of the fixed sensor array is identical regardless of the model used. With the augmented model (see Figure 5.13b), the mobile and random sensors benefit from the model augmentation because they can measure ashes before fire. In addition, the faster they move, the further they can measure burnt trees from their initial position. Comparing the two mobile sensor networks, it can be seen that increasing the speed increases the synchronisation performance. Furthermore, as the random sensors can be considered as mobile sensors with a very high speed, it can be easily conjectured that the random sensor network is the limit of the mobile sensor network when increasing the speed. Thus, without adding any additional behaviour, the combination of augmented model and random sensor network seems to be the most suitable to solve this problem. It is also important to note that if we want to use the optimised synchronisation, it works when the sensors are moving fast. If they are too slow, they will not be able to reach the error area before the fire has spread on a large part of the lattice, which makes the optimised synchronisation useless.

In section 4.4.3, we presented a method of coordinating the sensor network when the initial error is small. We were able to apply the results to the fire propagation model by adding a dimension to the lattice. Therefore, the error propagation no longer has a triangular shape but a pyramidal shape with a square base (because this is the shape of the neighbourhood). The height of the pyramid represents the time. At each iteration, the error can propagate to 8 other cells (see Figure 2.1b for the shape of the neighbourhood), but to only 1 in each direction (including the diagonals). By making this slight change, we are able to apply the optimised synchronisation method to the forest fire propagation model. In Figure 5.14 we have plotted the average evolution of the normalised synchronisation error for the classical model and increased using the classical and optimised synchronisation (presented in section 4.4.3). Figure 5.15 shows the same error but on a semi-log scale for a more detailed study of the evolution of the error.

Firstly, we notice that the time at which the error starts to reduce is reduced, the type of model used seems to have no impact when used with the optimised synchronisation. The time is = 5 for the synchronisation and = 10 and = 17 for the classical synchronisation with respectively the augmented and classical model. This decreasing time is the same as for the use of state estimation with reconstructibility (see Figure 5.10), but we will compare the two methods in more detail in the next section. Then, we notice that the decrease of the synchronisation error is stronger with the use of the optimised synchronisation (which is even more important when paired with the augmented model), this can be seen very well in Figure 5.15, where the decrease is linear for the classical synchronisation and exponential for the optimised one. However, the impact of the optimised synchronisation is lower when the time increases. At = 20 the decrease becomes linear similar to the one using the classical synchronisation. The use of the augmented model results in a 17% faster error decrease, which explains why the error of the augmented model with the classical synchronisation catches up with the classical model with the optimised synchronisation (at = 97). On the other hand, none of the four configurations provide a null error at = 100. Finally, it can be concluded that the use of the augmented model with optimised synchronisation seems to be the most suitable for monitoring, as the rapid reduction of the synchronisation error provides a faster information on the fire propagation. As in the case of rule R30 (see Figure 4.20b), the synchronisation error with the augmented model and the optimised synchronisation at time = 100 is not perfect because there are a number of simulations (1.9% at = 50, 0.63% at = 75 and 0.17% at = 100) where the error is non-zero. In 70% of the cases, these are small errors that group fewer than 10 cells. To compensate for this, the coordination should be improved and the areas should be measured in a regular and balanced way. This will ensure that the fire front is detected sooner and the earlier it is detected, the more effective the optimised synchronisation is due to the error zone size increasing with time. To enable good sensor management, [START_REF] Schlotterbeck | Decentralized estimation of forest fire spread using mobile sensors[END_REF] use a set of forces to ensure that the sensors are evenly distributed over the space. This method could be adapted to this model by making the empty areas have a repulsive force as borders can have. Other methods such as fair space division have been studied in (Plénet et al., 2020b) allowing sensors to move randomly but only within a given area. In this way, the sensors share the space, but can also concentrate when the error is detected so that optimised synchronisation can be applied.

In this section, we have been able to develop an efficient state estimator using synchronisation. To do this, we had to augment the replica model to take into account a model-specific phenomenon. We also studied the types of sensors and concluded that the use of the augmented model with random sensors was the best performing pair. Finally, we implemented the optimised synchronisation presented in chapter 4 for the monitoring of forest fire spread. In the next section, the last one concerning the forest fire study, we will compare the results of the state estimator presented in this section with the one presented in the previous section.

Conclusion

In the previous two sections, we have developed two state estimators. The first one is based on reconstructibility while the second one uses synchronisation. In Figure 5.16, we have represented the average evolution of the errors in both cases. It is immediately noticeable that the performances are similar, the synchronisation admits a faster decrease of the error between = 5 and = 15, but has a slightly higher error at = 30. In the case of synchronisation, this error will continue to decrease as more measurements are taken by the sensors. On the contrary, the error in the case of state estimation with reconstructibility will be stable. In both cases, these errors represent a small portion of the simulations that have low error rates. However in the case of synchronisation this error may be over the large, connected, forest area.

Although the average performance of both estimator is very similar, the two state estimators are very different. The first one, based on reconstructibility, uses a fixed sensor network, so it could be improved to make the sensors move and measure isolated areas. However, the state estimator algorithm is much more algorithmically heavy as it requires the simulation of several thousand configurations simultaneously.

On the other hand, the synchronisation uses a network of mobile sensors with the presence of coordination (optimised synchronisation). The choice of one method or another will depend on the types of sensors available and the computing power available for the state estimator. On one hand, the characterisation of reconstructibility is more interesting as it ensures that the state will be reconstructed correctly. However, as long as the state estimator is not error tolerant this method cannot be applied in consideration of real scenarios. In addition, reconstructibility must be assessed for every small variation in the system, including wind, forest topology, etc. On the other hand, synchronisation, provides more freedom in coordination as reconstructibility does not need to be verified. It offers an easier framework to use decentralised coordination method such as multi-agent systems or wireless sensor network. The study of synchronisation through statistics must be done with care to avoid scenarios where the error does not synchronise at all.

With this example, we were able to present a method for setting up a state estimator. We started by making a trivial model of fire propagation. Then, we were able to study its observability and reconstructibility as well as the synchronisation. We were able to compare the two estimators in terms of performance and the advantages and disadvantages of each. In the next two examples, we will address notions not used in this example, such as the decentralisation of the observation or the observability of the ACA.

MONITORING OF A ROAD NETWORK THROUGH A TOLL BOOTH

In this example we will study the observability and reconstructibility of a road traffic model. We plan to use fixed sensors as these are already present on the road as radar or road tolls. Several road traffic models have been developed since the 1970s, the most famous being the ECA R184. However, the lack of granularity in traffic modelling has led to the use of other types of models. [START_REF] Nagel | A cellular automaton model for freeway traffic[END_REF] propose a specific traffic model for motorways by adding the notion of speed. With this model, they manage to model typical traffic behaviours such as traffic synchronisation or wide moving jams. Several years later, [START_REF] Knospe | A realistic two-lane traffic model for highway traffic[END_REF] extended this model to a two-lane road. Other models are proposed, especially for city traffic where the modelling is based on the presence of traffic lights. With a CA model, [START_REF] Brockfeld | Optimizing traffic lights in a cellular automaton model for city traffic[END_REF] propose to optimise traffic lights to maximise traffic in cities.

Usually, a road has unidirectional dynamics in the direction of traffic, in the case where there are several lanes, each of these have little interaction with one another. We could therefore conveniently apply observability or reconstructibility because of the few boundary cells. However, the complexity of this method requires the use of a small number of cells and states, which is why we will study the simplest traffic model, the ECA R184.

Presentation of Wolfram Elementary Rule R184

R184 is one of the most used of Wolfram's elementary rules. It has been used in many fields to model physical systems such as 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]. As with all ECA, R184 is a boolean, one-dimensional, deterministic CA but there are a number of variants of this rule. Rosenblueth and [START_REF] David | A model of city traffic based on elementary cellular automata[END_REF] augmented the model to simulate traffic light intersections. The cells of the intersection change their rule as a function of time to allow vehicles to pass or not. This method will be presented in detail in section 5.3.3 when we study the road network of a city. [START_REF] Higashi | Rule 184 fuzzy cellular automaton as a mathematical model for traffic flow[END_REF] have transposed the R184 rule to Fuzzy Cellular Automata, which allows them to have a car density rather than a boolean value. [START_REF] Nishinari | Analytical properties of ultradiscrete burgers equation and rule-184 cellular automaton[END_REF] showed that R184 is a special case of the discretisation of the Burgers equation, a partial differential equation used for modelling gas dynamics, acoustics or road traffic. But finally, we will focus on the simple case of the ECA R184 for the moment.

In R184 as a traffic model, the state of the cells represents the presence, or not, of a car as shown in Figure 5.17. All cars move in the same direction, in this case to the right, and they can only move forward if they have an empty space in front of them. Therefore, to have a continuous flow of cars, you need a maximum of /2 cars for a lattice of cells otherwise traffic jams will appear. On Figure 5.18, we present two simulations of the CA R184-100-PB, in the first case, the traffic jam (in black) disappears because the road is not saturated. In the second case, on the contrary, the traffic jam only moves in the opposite direction of the cars. On the opposite to what we were able to do in the previous example, we cannot make simplifications on the initial configurations of the system. The number and position of vehicles is unknown at the initialisation. Because of this, we cannot study a CA with more than a dozen cells. Therefore, we will study the ECA R184-10-PB. The periodic boundary ensures that there are always cars in the system, the cars leaving the system are also entering it at the other end. Thus, using definition 2.1, the CA can be defined as :

• L = 0; 9 • S = {0, 1}
• N ( ) = { -1 , , +1 }, with the periodic boundaries conditions -1 = 9 and 10 = 0 .

• : (N ( )) ↦ → +1 ( ) = ( -1 ) ⊕ ( ) • [ ( +1 ) ⊕ ( -1 )], with respect to the modular arithmetic of S as presented in eq. (2.6).

Now that we have defined CA, we can study its observability and reconstructibility. We will also use decentralised reconstructibility in order to increase the size of the road we can monitor. Then, in the last section, we will extend this model to have a 2-dimensional road network with intersections in order to study its reconstructibility.

Study of Observability and Reconstructibility

We will study the observability and reconstructibility for the ECA R184-100-PB presented in the previous section. As this CA is non-linear, we will use the results from section 3.3. However, as we are studying all initial configurations and it is not very large, we will use the matrix approach presented in section 3.3.1. The matrix of the transition function is of size 1024 × 1024 and this is quite a reasonable size for doing multiplication operations. We did not construct the matrix with the methods using the semi-tensor product, but as an adjacency matrix, i.e. by evaluating which configuration +1 corresponds to ( ).

This CA poses another problem regarding observability: it cannot be evaluated with few sensors. Indeed, to differentiate the two initial configurations presented in Figure 5.19, 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. Because of this, we will not try to find a sensor network that ensures the observability but only 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. However, as our objective is to study a large road network through decentralisation, we will place, as shown in Figure 3.5, a sensor at each end of the lattice. Thus, by measuring the 0 and 9 cells with fixed sensors, the sensor network can be defined as :

• L = {0, 9} • : := ( ) = ( 0 ) ( 9 )
To verify the reconstructibility of the CA, we will first construct the observability matrix from the matrix and the matrix of . Then observability and reconstructibility are respectively verified with theorems 3.5 and 3.6. As we cannot apply the Cayley-Hamilton theorem, we start by assessing the observability and reconstructibility with a minimum time horizon = 0 and will increase it gradually until one of them is verified. If neither the observability nor the reconstructibility is verified by = 20 we will stop here and look for another sensor network. In addition, to the evaluation of observability and reconstructibility, we count the number of unobservable and unreconstructible configurations and plot this number as a function of the time horizon in Figure 5.20. After a few seconds of simulation, we find that the system is reconstructible (but not observable as we expected) from = 13. Increasing the observation horizon does not reduce the number of unobservable configurations beyond 75% of the total number of configurations. 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. Instead, we plan to divide the CA of 1, 000 cells into several sub-observers of equal, smaller sizes. However, the complexity of the decentralised reconstructibility presented in section 3.4.2 is far too important to for a sub-observer of size 10. Indeed, with a time horizon = 13, there will be 4 13 possible boundary trajectories. We must use a sub-observer of smaller size in order to decrease the reconstructibility time horizon. Therefore, we will use 200 sub-observers with 5 cells, each of them measured by the sensor topology shown in Figure 3.5, one sensor at each end of the lattice. Similarly to what we have done for the study of reconstructibility, we have no constraint on the time horizon , except that it must be larger than 5, the time needed to ensure reconstructibility if we consider the previous system with only 5 cells. Figure 5.21 shows the evolution of the percentage of boundary trajectories that are not reconstructible, i.e. boundary trajectories for which the CA is unreconstructible. The sub-observer is never reconstructible for a time horizon shorter than 12. Beyond that, the time to check reconstructibility is too long for our machine. As an attempt to still ensure reconstructibility, we have added a sensor in the middle, the 2 cell, of the sensor network. Even though the number of unreconstructible trajectories is lower, the system is still not reconstructible. The reason for this is that if the right-end boundary cell is in the 1 state for the entire duration, then the cars in the CA cannot move out of the lattice. It is therefore impossible to measure all of them and we cannot distinguish between the 00001 and 00011 configurations. And this is true for a time horizon as large as it is. To achieve reconstructibility, we would need to be able to detect when a large traffic jam is forming and optimise the placement of the sensors to ensure that we measure the blocked cars.

As a small part of the configurations are unreconstructible, we could do as in the previous example and perform a state estimator and consider that it will work. However the unreconstructible configurations represent the whole lattice, not just small isolated areas as in the fire propagation model. The state of the sub-observer (except for the measured areas) will be unknown. With the use of measured boundaries, this error will not propagate and can be identified by the state estimator if the state does not converge. If the boundaries were not measured, the error would propagate throughout the system and affect the proper functioning of the observation. In this case, it would be necessary to think about implementing error management. 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.

Extending the Model to New York Traffic

The model studied in the previous section represents a straight road without any particular signalling or slowing down (other than that caused by overloading the network). Rosenblueth and Gershenson (2011) have added the possibility of having intersections governed by traffic lights. Their model uses only elementary rules, R184 for traffic roads and R252 and R136 for traffic lights. As the traffic lights change with time, so do the cell rules (see Figure 5.22). The central cell does not change its rule but its neighbourhood depends on the time, it always contains the two cells that are not restricted by the lights. As the transition function will change over time, the evaluation of observability and reconstructibility is time-dependent. Indeed, the matrix will be different depending on the starting time, which was not the case with a time-invariant transition function. For this example, we will use the lattice shown in Figure 5.22, i.e. with 13 cells.

We will use periodic boundaries, the vertical and horizontal lines will be looped on themselves. As far as the sensors are concerned, we will use 5 of them: one on each end and one in the centre, on the intersection. In the same way as before, we will evaluate the observability and reconstructibility using the method presented in section 3.3.1. Due to the large number of configurations, we will use the sparse matrix representation for the matrix. In Figure 5.23, we show the evolution of the number of unobservable/unreconstructible configurations as a function of the time horizon. We see that the system is unreconstructible from = 30 but not observable. Given the time needed to ensure reconstructibility, we will not study decentralised reconstructibility.

If we ever manage to ensure decentralised reconstructibility for both the intersection and the road (see previous section), then we would be able to build a square road network, similar to the one in Manhattan. Indeed, observability and decentralised reconstructibility work as long as the values of the boundaries are provided to them, no matter which CA is next door. This means that a modular state estimator can be constructed from elementary blocks. The time horizon for the reconstructibility of the system will be the longest horizon of all sub-observers.

Conclusion

In this example, we have studied R184 and in particular its interpretation as a road traffic model. We were able to study its observability and reconstructibility with the theorems 3.5 and 3.6 because there were no constraints on the initial conditions. The observability could not be verified because it requires too many sensors. Once the reconstructibility was verified, we wanted to verify the decentralised reconstructibility in order to increase the size of the studied route. For this purpose we want to divide the lattice into sub-observers of 5 cells. However, the reconstructibility could not be verified for the chosen time horizon and can never be verified with the chosen sensor network. The use of toll booths (i.e. static sensors at the beginning and end of the road) cannot ensure reconstructibility. A different sensor network with one or more sensors, mobile or not, between the sensors at the ends must be used. The purpose of these additional sensors would be to measure the state of the traffic jam when the tolls are no longer effective. In addition, we could put conditions on the values taken by the borders so that they are more faithful to reality. A traffic jam cannot last forever.

Subsequently, we chose to study an extension of the model proposed by Rosenblueth and [START_REF] David | A model of city traffic based on elementary cellular automata[END_REF] which allows to model an intersection managed by road traffic. We were able to verify the reconstructibility of this CA using 5 sensors. This intersection model allowed us to demonstrate the use of reconstructibility for a CA whose dynamics depend on time. In the end, if we had been able to verify the reconstructibility of the two models studied, we would have 2 sub-observers that would have allowed us to build a modular state estimator for a square road network similar to that of New York.

RANDOM NUMBER RECONSTRUCTION

In cybersecurity, pseudo-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 RNG depends on both the probability distribution and the predictability of the generator. It is evaluated using randomness tests which allow the quality of the RNG to be assessed according to several criteria. Among these tests, the best known are the Diehard tests [START_REF] Marsaglia | Diehard: a battery of tests of randomness[END_REF] and the TestU01 [START_REF] Pierre | Testu01: Ac library for empirical testing of random number generators[END_REF]. As a crucial element of cybersecurity, RNG are 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 past or future 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 volume 43[END_REF]. The local, simple and regular interactions of CA make them a good way integrated at large scales. Initially, CA RNG are one-dimensional [START_REF] Pal Chaudhuri | Additive cellular automata: theory and applications volume 43[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 volume 43[END_REF]; [START_REF] Tomassini | On the generation of highquality 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 highquality random numbers by two-dimensional cellular automata[END_REF].

In this example, we will use the observability of affine cellular automata (ACA) to reconstruct present, past and future random numbers using information obtained by a random number generator attack. The objective of the attack is to obtain partial information on the state of the CA RNG that will subsequently be used to apply the results of section 3.2. 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 which will depend solely on the information obtained by the attack. Of these three examples, the first will use knowledge of a single 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. Throughout these examples, we will use the [START_REF] Tomassini | On the generation of highquality random numbers by two-dimensional cellular automata[END_REF] 2D CA RNG which we define in the next section.

Cellular Automata Random Number Generator

For this example, we will study a CA RNG generating high quality random numbers proposed by [START_REF] Tomassini | On the generation of highquality 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 [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 bits random number every iteration rather than a 64 hexadecimal digits random number every 4 iterations.

The CA RNG is defined as follows:

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

• S = {0, 1}

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

In their paper, Tomassini et al. describe three boundary conditions: 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 in the middle represents the random number. In our example, we will use the fixed (full) version with a zero value at the boundaries.

The CA RNG of Tomassini et al is a hybrid CA, the local transition function depends on the cell position. Regardless of the rules number, the transition function (5.3) is an affine map. Therefore every CA that respect Tomassini's definition can be represented with the state representation (2.12). However, as the CA RNG is hybrid we cannot construct the matrix as a Toeplitz matrix (see section 3.2.3). The "shape" of the matrix remains the same but the value of the change depending on the value of the rule (e.g. 0 is the value of the bit ).

To construct these CA RNGs, Tomassinni et al. use a genetic algorithm with random tests as fitness function. Moreover, the presence of large cycles is also a guarantee of quality because it allows the generation of a very large number without "looping". Hence, they are able to easily generate CA RNG with different sizes that generate good quality random numbers (from the point of view of DieHard tests).

Additionally, the CA RNG presented in Figure 5.24 is reversible, which does not seem to be a property sought by the authors but rather a consequence of the criteria of the method used.

In the following sections, we will present two purely theoretical attacks which aim to show a use of Kalman criterion. In each of the examples, we will briefly present the attack and the associated output operator that reconstruct the state of the system. However, the details of the calculations will not be presented due to the large number of cells.

Regular Measurement Attack

In this first example, we study the observability of the CA RNG where the sensors have partial information on the generated random numbers. The aim is to study the observability when the sensor measures one bit of information on each iteration. We could have used more information bits, which would have potentially decreased the observability time horizon as a consequence of the Cayley-Hamilton Theorem. As specified in the introduction of this section, we are not interested in the "physical" method used to obtain the information on the CA RNG, for example this could have been recovered using an 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].

To reconstruct random number stream, we need only one bit of information on the random number at each time step. The measurement can be done on a single digit (read digit as the position of the bit in the random number) or can change with time. The only information needed is the position of the measured digit at each time step. Therefore, we can create the operator which corresponds to the digit of the random number (or the cell associated with this bit) measured at time . The operator is of the form : = 0 . . . 0 1 0 . . . 0

, where the 1 corresponds to the measured bit. Before assessing observability, we will check whether the output operator is adapted for observation. As we specified in the previous section, Tomassinni's CA RNG are constructed to be reversible and therefore injective. From definition 2.7, the injectivity of the CA guarantees that all output operators are suitable for observation. Moreover, remark 2.3 specifies an equivalence between observability and reconstructibility, so it will not be necessary to evaluate reconstructibility if observability is not verified.

Then, we need to know the operators associated with the measurements and from there construct the observability matrix over a time horizon 64. The system is observable (i.e. rank = 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. Using the corollary 3.1, it is possible to find the initial generated random number (i.e. the state 0 ) and to deduce the future generated random number until the CA RNG is initialised with another seed (a pseudo-random generator process that consists of manually setting the state of the CA RNG).

Furthermore, since we know that the CA RNG is reversible, it is possible to deduce the previous states of the system. Indeed, the matrix is invertible and given the initial state 0 reconstructed using the Kalman criterion, we can express all states as:

= • 0 + -1 • - = -• 0 --1 •
where -is the inverse of to the power and -1 = =1 -In other words, once we have successfully obtained a random number, we are able to deduce all future and past random numbers. In the next example, we deal with the case where the sensors cannot obtain a particular bit but a property of the whole number, the parity bit of the random number.

Parity Attack

The objective of this attack is to reconstruct the random number sequence using only the parity bit of the random numbers. The parity bit is the binary sum of all the bit of the number. 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 state of the system can be represented by the following:

         +1 = + = 64 =0
The sum uses binary modular arithmetic.

The output operator associated with parity is a row vector composed of 64 1 which does not depend on time. From there, the observability matrix can be computed with = 64 and it is full rank matrix. The system is observable with the parity measurement, which allows us to reconstruct the initial state as well as the past and future states due to the reversibility of the CA RNG.

Conclusion

In those two examples, we have been able to reconstruct the random number stream from the partial information 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 those examples was to show the usefulness of observability for the reconstruction of a random number stream in a RNG attack context. Although very efficient to reconstruct the random number stream, this method still have shortcomings: the dynamic of the CA RNG must be perfectly known; the random number seed (i.e. the state of the CA) must not be manually modified by the user during the measurement; the CA RNG must not have non-linearity (which has been recommended in [START_REF] Meier | Nonlinearity criteria for cryptographic functions[END_REF]). By implementing one of the above cases, the application of the Kalman criterion for this CA RNG becomes impossible. The use of a non-linear CA RNG is also possible because the number of cells is large enough to not allow the use of the results of section 3.3.

CONCLUSION

In this chapter we were able to apply the observation methods of the thesis to three concrete examples. The first one on a forest fire model, the second on a road traffic model and the third on a random number generator.

In the first example we were able to apply and compare the two observation methods presented in the thesis. The first one using reconstructibility and the second one using synchronisation. The forest fire model chosen was very simple, but the placement of the sensors to ensure reconstructibility and observability was not trivial. It will be necessary to set up methods to place the sensors in order to avoid a trial and error placement which takes a lot of time, especially considering the number of sensors.

The second example was a demonstration of the use of decentralised observability. The example also aimed to illustrate how decentralised observability could be applied to the construction of a modular road traffic network. However, we could not solve this problem for the chosen road traffic model. The verification of decentralised observability or reconstructibility (or more generally of a CA with unknown boundaries) is more time consuming and complex than for other types of boundaries.

The last example served as an illustration for the observability ACA for the observation of a random number generator. In this example, we easily manage to reconstruct the random number sequence from very partial information on the generated numbers. This state estimator can greatly facilitate the exploitation of a security vulnerability. We have presented several suggestions to prevent this kind of attack by making it impossible to use this reconstruction method.

The next and final chapter serves as a conclusion to the thesis. It highlights the main contributions of the thesis and presents some ideas for continuing the work on the observation of CA.

CHAPTER 6

Conclusions and Perspectives

The observation of natural phenomena is a crucial issue for the understanding of the world around us, especially those with important spatial dynamics. In the introduction, we have seen that cellular automata are good alternatives to PDE to describe spatially distributed systems. This thesis lays the foundations for the observation of CA models, by presenting two profoundly different tools: observability and synchronisation.

MAIN CONTRIBUTIONS

This thesis proposes 4 major contributions: the definition of observability for CA, the generalisation of the Kalman condition for ACA, the adaptation of the observability criterion of BN to CA, and the formalisation of the synchronisation as a state estimator. In the following paragraphs, we will describe each of these contributions in more details.

Firstly, we formalised the notions of observability, reconstructibility and adaptability for cellular automata. Observability and reconstructibility have already been defined for other types of systems (linear time invariant system, boolean network, etc.) in the past. The contribution of this thesis lies in the transposition of these characterisations to cellular automata. We have also described the compared injectivity, a special form of injectivity with respect to another function which is intimately connected to the reconstructibility. Then, we have formalised the notion of adaptability from the work of [START_REF] Laschov | Observability of boolean networks: A graph-theoretic approach[END_REF] to derive a necessary condition for observability that can be checked before the construction of the output sequence. This notion is particularly important as it plays a direct role in the placement of sensors when we wish to ensure observability.

Secondly, we generalised the Kalman rank condition as an observability criterion for additive and affine CA. We proposed similar criteria for adaptability and reconstructibility. These are not a condition on the rank, but respectively on the kernel of the output or observation matrix. The former requires that the kernels be disjoint and the latter requires the inclusion of the kernels. The observability 137 and reconstructibility criteria are also completed by a corollary that provides the possibility to reconstruct the initial or current state of the system from the output sequence.

Thirdly, we have improved the observability and reconstructibility criteria of Boolean networks by benefiting from the advantages of CA. This allowed us to develop an algorithm that verifies both observability and reconstructibility for each of the initial configurations. Unlike other methods, this algorithm can take into account conditions on the initial configurations. This greatly reduces the algorithmic complexity by providing the ability to evaluate observability or reconstructibility of CA with a large number of cells. In the case where this reduction does not apply or does not reduce the complexity sufficiently, we have implemented a method for decentralising the observability analysis which provides a linearisation of the complexity by dividing the problem into smaller problems. This method works practically only on one-dimensional CA as it requires a large number of sensors for higher dimensions.

Lastly, we have formalised the synchronisation of CA as a state estimator. This approach is radically opposed to the previous one as we do not seek to check beforehand if the observation will work but only to study statistically its performance. We have also developed an optimised method that provides coordination of mobile sensors if the initial error is composed of a single erroneous cell. In the forest fire propagation example, the optimised synchronisation and the reconstructibility approach achieve similar average observation performance.

This thesis lays the foundation for CA observation by providing definitions of observation and two methodologies for state estimation. However, we are still a long way from the deployment of a sensor network using cellular automata for monitoring physical systems. We present hereafter the perspectives to continue this work. We divide them temporally in the order in which we suggest they should be carried out.

PERSPECTIVES FOR SHORT-TERM RESEARCH

Extension to Continuous State CA

Many CA such as the fire model of Karafyllidis and Thanailakis describe the state of the cells by a continuous value. This type of model has by definition a greater accuracy of modelling than the finite state models. However, they do not fit the definition of El Yacoubi and are therefore not taken into account in this work. The Kalman criterion and the synchronisation still appear to be applicable. The former can be applied as it does not require the finiteness of the state but of the number of variables, i.e. that the lattice is finite. The synchronisation can be applied with continuous values but the properties need to be verified.

For the study of non-linear CA, it would be necessary, however, to seek inspiration once again from classical control theory and its study of non-linear systems which has been widely studied for several decades. Another alternative would be to quantify the variable, this would provide, when the state is bounded as in the Karafyllidis and Thanailakis model, a way to use fuzzy logic and thus use the results of this thesis.

Probabilistic Observability and Reconstructibility

At the end of Chapter 3, we introduced probabilistic observability and explained that it might support the use of sub-observers on multidimensional CA. It is necessary to study this since we have simply presented the idea and some definitions of probabilistic observability. Furthermore, establishing criteria for probabilistic observability and reconstructibility would provide a direct way to study probabilistic CA. Although they are less used than deterministic models, they provide a means of modelling features that are impossible for the deterministic one.

Controllability of Cellular Automata

In this thesis we studied the observability and reconstructibility of CA, but not the controllability. Many applications combine the two, hence it is necessary to study this issue. In addition, for linear time invariant systems these two concepts are decoupled, i.e. they can be studied separately. It has already been studied by [START_REF] Dridi | A graph theory approach for regional controllability of boolean cellular automata[END_REF], but it remains to establish the connection between the two so that a state estimator can be made that is used for system control. The Kalman criterion can be applied in the same way for controllability and it has also been studied for Boolean networks. [START_REF] Bagnoli | Control of cellular automata[END_REF] have also studied synchronisation as a controller.

PERSPECTIVES FOR INTERMEDIATE-TERM RESEARCH

Error tolerance

Error tolerance is an essential element of the state estimator. Without it, a measurement error or uncertainty in the model could result in the incorrect reconstruction of the state. In classical control theory, state estimators are constructed to respect error margins that guarantee a certain tolerance to error. In order to apply CA estimation to actual problems, it is necessary to develop these notions of error margins for the estimators presented in this thesis.

=

( 2 ⊗ )( 8 ⊗ )( 4 ⊗ [4,2] )( 2 ⊗ [2,2] ) ( 2 ⊗ )

From definition B.1, we obtain that swap matrices [2,2] and [4,2] are :

[2,2] =        
1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1

        [4,2] =                
1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1

               
Considering the matrices , and defined above, we obtain that is:

=                
0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0

               
We can check that the matrix is correct by looking at the adjacency matrix of the graph in Figure Figure 3.3. It is the transpose of the matrix which confirms that the matrix is correct.

In this example, we were able to construct the matrix algebraically. We did the calculations by hand, but using equation (B.5), we can set up an automatic method. However, the number of operations to calculate is large compared to the number of cells, but these could be optimised with the use of sparse matrices.

F . .

 . Different neighbourhoods for two-dimensional lattice of square cells as a function of the -norm and the distance . Neighbourhoods from left to right: Von Neumann of distance 1; Moore of distance 1; Von Neumann of distance 2; and Moore of distance 2.

  Examples of the boundary conditions for a two-dimensional cellular automaton with a 3 × 3 lattice of square cells. The letters from to represent the cells of the CA and the cells on either side of the CA represent the boundary cells.

  Truth table of the transition function of the Wolfram's ECA 90, or simply rule 90. The first row represents the possible states of the neighbourhood at time and the second row represents the state of the central cell at time + 1 corresponding to the neighbourhood of the column.

F . .

 . Generation of the Sierpiński triangle with R 6. Evolution of R 6--PB from a single black cell. The black cells represent 1 and the white cells represent 0. Time is going down on the vertical axis.

F . . R 8

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

Figure 2 . 6 )

 26 Figure 2.6), a species of sea snail; R184 can model a very simple road network (see Figure 2.5) or the deposition of particles on a surface[START_REF] Chopard | Cellular automata[END_REF].

F . 6 .

 6 Example of the evolution of R --PB for a time horizon of 30 and a picture of the Conus Textile shell. Image from Richard Ling on Wikipedia.

  State transition diagram of the elementary Wolfram cellular automaton R 8 --PB. This CA has 5 different cycles: 2 of size 1, 2 of size 4, and 1 of size 2.

  Example of evolution for ECA to show the behaviour of different classes of CA presented by Wolfram. Time is going down on the vertical axis for 30 time step.

F . .

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

Contents 3 . 1

 31 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.2 Kalman Criterion for Additive and Affine Cellular Automata . . . . . . . . 40 3.2.1 Affine and Additive State Representation . . . . . . . . . . . . . . 40 3.2.2 Conditions for Observability and Reconstructibility . . . . . . . . 44 3.2.3 Tools for the Verification of the Kalman Criterion . . . . . . . . . 51 3.3 Observability and Reconstructibility for Non-Linear Cellular Automata . . 54 3.3.1 Observability and Reconstructibility of Boolean Network . . . . . 54 3.3.2 Binary Relation Representation of Cellular Automata . . . . . . . 62 3.3.3 State Estimator for Non-Linear Cellular Automata . . . . . . . . . 67 3.4 Decentralisation of Observability and Reconstructibility . . . . . . . . . . 71 3.4.1 Observability and Reconstructibility of Sub-CA . . . . . . . . . . 72 3.4.2 Deterministic Method for Distribution . . . . . . . . . . . . . . . 74 3.4.3 Probabilistic Model for Estimated Boundaries . . . . . . . . . . . 75 3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  Simple example of a three-variable Boolean network described by the graph and the equation system.

F . .

 . State transition diagram of the Boolean network in Figure . . The Boolean variables are arranged in the order for the representation of configurations.

  Example of an observability graph for the BN of Figure . . The continuous edge represents an output of 0 and the dashed edge an output of 1. The outputs of (a) and (b) correspond respectively to the Boolean variables and .

F . .

 . A one-dimensional CA subdivided into sub-CA. Grey cells are measured by a sensor.

Figure 4 .

 4 1 shows an example of synchronisation for the ECA R110-100-NB.

Figure 4 .

 4 2 describes the evolution of the normalised synchronisation error from the synchronisation example presented in Figure4.1. This new expression for the

  Example of random synchronisation of the ECA R --NB for a time horizon = 150 and a coupling probability = 0.2. The black cells represent 1 and the white cells represent 0. Time is going down on the vertical axis. Evolution of the normalised synchronisation error of the ECA R --NB for the example given in Figure . . synchronisation error makes it easier to represent synchronisation in a temporal perspective in order to analyse the results. It would have been difficult to deduce the time at which the replica is synchronised with the driver from Figure 4.1.

  Example of the synchronisation error for different coupling probabilities for ECA R --NB. Time is going down on the vertical axis for 100 time step. The initial configurations of the driver and the replica were randomly initialised but were unchanged for the four examples.

  Evolution of the normalised synchronisation error (continuous) and the synchronisation rate (dashed) at time = 150 as a function of the coupling probability for the ECA R --NB. The mean is computed through 10 4 simulations.

  Evolution of the normalised synchronisation error at time = 150 of the ECA R --NB for different types of sensors. The mean is computed through 10 4 simulations.

6 .

 6 Evolution of the normalised synchronisation error at time = 150 of the ECA R 8 --PB for different types of sensors. The mean is computed through 10 4 simulations.

  Normalised synchronisation error as a function of time of the ECA R 8--PB for different initial error 0 . The mean is computed through 10 4 simulations.

  Evolution of the synchronisation error for ECA R 8--PB from a single cell error ( 0 = 1%). The time is represented on the vertical axis. A black pixel is an erroneous cell in the lattice of the replica.

  Value of the asymptotic behaviour of the normalised synchronisation error as a function of initial error 0 of the ECA R 8--PB. The continuous lines consider only the asymptotic synchronisation whereas the dashed lines include both asymptotic and total synchronisation. The mean is computed through 10 4 simulations.

  Examples of synchronisation error from a single erroneous cell for ECA of different classes. Time is going down on the vertical axis for 25 time step.Through simulations with the ECA R18, we seek to model the propagation of the synchronisation error as a function of the coupling probability . First, we present on Figure4.11 the typical synchronisation error propagation dynamics for R18 from a single erroneous cell.

  Evolution of the error for elementary R 8--NB from a single erroneous cell. Time is going down on the vertical axis for 250 time step.

F . .

 . Schematic of the theoretical propagation triangle of the synchronisation error from a single initial error cell.

  Mean and standard deviation of the error spread ratio and the error shift ratio as a function of coupling probability for the ECA R 8--NB. The mean and standard deviation were computed over 10 4 simulations.

F . 6 .

 6 Evolution of the normalised synchronisation error as a function of time from simulations of the R 8--PB as well as the two theoretical cases when is constant or follows a normal distribution. Schematic of the theoretical propagation triangle of the synchronisation error from two initial error cells.

  Evolution of the normalised synchronisation error as a function of time from simulations of the R 8--PB as well as the two theoretical cases when is constant or follows a normal distribution.

  Evolution of the normalised synchronisation error at time = 750 of the ECA R 8--PB for the regular and the optimised synchronisation. The mean is computed through 10 3 simulations.

  of the normalised synchronisation error at time = 750 for different ECA for the regular and the optimised synchronisation. The mean is computed through 10 3 simulations.

  Definition of the neighbourhoods for the Karafyllidis and Thanailakis fire propagation model.

  Successive fire fronts for different scenarios. The unit on both axes are arbitrary. Image taken directly from(Karafyllidis and Thanailakis, ).

5 F . .

 5. (a) Von Neumann and = 1 (b) Moore and = 1 (c) Von Neumann and = 0.7 (d) Moore and = 0.Example of the mean evolution of the fire front as a function of the chosen neighbourhood and the tree density at initialisation. Means are obtained over simulations.

  use three different plants with different combustion period: tree ( = 200), shrub ( = 70) and grass ( = 1). This increase in the transition period can be modelled in different ways. The first, which respects definition 2.1, consists in adding intermediate states (e.g. burning tree 1 to burning tree 200). The second requires the use of memory-based CA, a variant of CA where the next state

F . 6 .

 6 Example of the evolution of the fire front according to the wind direction. Simulations are obtained through the mean over simulations.

  Percolation of the trivial CA as a function of the neighbourhood. The simulations were performed on a CA of size 100 × 100 with an average over simulations.

  Topology of the forest that will be used throughout this example. The forest is of size 100 × 100 and built with density = 0.5.

  Map of the sensor network and the non-observable and non-reconstructible configurations. The non-observable configurations are shown in red and the non-reconstructible configurations in blue.

F . .

 . Evolution of the normalised synchronisation error as a function of the time for the state estimation of the sensor network presented in Figure . a. The mean is computed through 10 3 simulations.

F . .

 . Diagram of the state changes of augmented trivial fire propagation model.

F . .

 . Evolution of the normalised synchronisation error as a function of the time for the classical and augmented fire propagation model. The mean is computed through 10 4 simulations.

  Evolution of the normalised synchronisation error as a function of the time for the classical and augmented fire propagation model. The mean is computed through 10 4 simulations.

F . .

 . Evolution of the normalised synchronisation error as a function of the time for the classical and augmented fire propagation model and the classical or optimised synchronisation. The mean is computed through 10 4 simulations.

F . .

 . Evolution of the normalised synchronisation error on a semi-log scale for the classical and augmented fire propagation model and the classical or optimised synchronisation. The mean is computed through 10 4 simulations.

F . 6 .

 6 Evolution of the normalised synchronisation error for the augmented/optimised synchronisation of Figure . and the state estimation of Figure . .

F . .

 . Wolfram elementary rule R 8 interpreted as a simulation of traffic flow. Each cell corresponds to a vehicle, and each vehicle moves forward only if it has open space in front of it. Image from David Epstein, English Wikipedia.

  Example of the evolution of R 8 --PB for different numbers of cars on the network. The dense black parts represent traffic jams. Time is going down on the vertical axis.

  Evolution of R 8 --PB for two similar initial configurations. Time is going down on the vertical axis.

F . .

 . Percentage of unobservable/unreconstructible configurations as a function of the time horizon for the ECA R 8 --PB.

F . .

 . Percentage of unreconstructible boundary trajectories as a function of the time horizon for the ECA R 8 --UB.

  (a) Cars move horizontally (b) Cars move vertically (c) Evolution of the CA for a single direction.

F

  Rule of the cells according to the traffic lights.

F . .

 . Percentage of unobservable/unreconstructible configurations as a function of the time horizon for the intersection CA.

Figure 5 .

 5 24 describes the transition function that 8 × 8 hybrid CA RNG proposed by Tomassini et al. ( ). The colour of the cells represents the transition function associated to this cell according to equation ( . ).

  applies to each cell as a rule whose value is defined by the 6-bit string XCNWSE which corresponds to the following transition function:+1 ( , ) = + • ( , ) + • ( -1, ) + • ( , -1 ) + • ( +1, ) + • ( , +1 )(5.3)Therefore, according to the previous generic transition function, the rules 15, 31, 47 and 63 correspond respectively to the transition functions :• +1 ( , ) = ( -1, ) + ( , -1 ) + ( +1, ) + ( , +1 ) • +1 ( , ) = ( , ) + ( -1, ) + ( , -1 ) + ( +1, ) + ( , +1 ) • +1 ( , ) = 1 + ( -1, ) + ( , -1 ) + ( +1, ) + ( , +1 )• +1 ( , ) = 1 + ( , ) + ( -1, ) + ( , -1 ) + ( +1, ) + ( , +1 )

  à l'observation des automates cellulaires. Les principales contributions de ce chapitre sont les définitions proposées d'observabilité, de reconstructibilité et d'adaptabilité, adaptées aux automates cellulaires. Ces définitions s'appliquent au cas de l'observation par un réseau de capteurs, fixes ou mobiles. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 Generalities on Cellular Automata . . . . . . . . . . . . . . . . . . 12 2.2.1 Brief History of Cellular Automata . . . . . . . . . . . . . 12 2.2.2 Definition of Cellular Automata . . . . . . . . . . . . . . . 13 2.2.3 Families of Cellular Automata . . . . . . . . . . . . . . . . 18 2.2.4 Properties of Cellular Automata . . . . . . . . . . . . . . . 26 2.3 Observability and Reconstructibility of Cellular Automata . . . . . 28 2.3.1 State Representation of Cellular Automata . . . . . . . . . 29 2.3.2 Sensors, Measurements and Output Operator . . . . . . . 30 2.3.3 Definition of Observability and Reconstructiblity . . . . . 33 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

	Contents
	2.1 11

  Table 2.2. In addition, it is possible to refer to RX-N, RX-B or RX if the number of cells or the nature of the boundaries are not specified.

	Boundary condition Null Fixed Periodic Reflexive Unknown
	Notation B	NB	FB	PB	RB	UB

T

. . The boundary conditions notation for writing ECA in the form RX-N-B where B is the term dedicated to boundary conditions. For example, the ECA of Figure

.

with cells and periodic boundaries has the notation R --PB.

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

Theorem 3.8. A CA A is observable (resp. reconstructible) by a sensor network H at time if and only if the binary relation R Θ (resp. RΘ ) is injective.

  Observability and reconstructibility relations for the BN of Figure . with a time horizon = 5.

				L = { }	L = { }
		01010)	(000, 01010)	(101, 01010)	(101, 01010)
		(001, 01010)	(001, 11010)	(101, 01010)	(101, 11010)
		(010, 01010)	(010, 00010)	(101, 01010)	(101, 00010)
		(011, 01010)	(011, 10110)	(101, 01010)	(101, 10110)
		(100, 10101)	(100, 00101)	(000, 10101)	(000, 00101)
		(101, 10101)	(101, 01010)	(000, 10101)	(000, 01010)
		(110, 10101)	(110, 01101)	(000, 10101)	(000, 01101)
		(111, 10101)	(111, 11011)	(000, 10101)	(000, 11011)
		(a) Observability Relation R Θ	(b) Reconstructibility Relation RΘ
	T	. .

Algorithm 1 :

 1 Verification of observability and reconstructibility of (A, )

	Function AssessObsRec (W, , Θ )
	Inputs :A set of admissible initial configuration W;
	a global transition function ;
	an output sequence operator Θ
	Outputs :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 initialised to true
	foreach 0 ∈ W do
	(Θ 0, , -1 ) ← Θ ( 0 )
	← ( -1 )
	if Obs[Θ 0, ] already exists then
	is_Obs ← false
	else
	Obs[Θ 0, ] ← 0
	if Rec[Θ 0, ] already exists then
	if Rec[Θ 0, ] ≠ then
	is_Rec ← false
	else
	Rec[Θ 0, ] ←
	return Obs, Rec, is_Obs, is_Rec

Lyrics from the refrain of Rick Astley's song Never Gonna Give You Up.iii

Data from Prométhée, which studies forest fires in Corsica, the PACA region, the Languedoc Roussillon region as well as in Ardèche and Drôme. More information on https://www.promethee.com

This quote is commonly attributed to Einstein, but it could be the paraphrase of an idea attributed to Einstein. More on this at https://quoteinvestigator.com/2011/05/13/einstein-simple/

More information on the Conus textile can be found on https://en.wikipedia.org/wiki/Conus_textile

A short definition of linear forms can be found on Wikipedia. https://en.wikipedia.org/wiki/Linear_form

The notion of compared injectivity is presented in appendix A. A definition and properties, including a characterisation for the linear case, are given there.

= ( 0 ) = ( 0 ), we have

When considering a two-dimensional (or higher-dimensional) CA, the matrix is no longer a Toeplitz matrix

A logical matrix is matrix representation of a binary relation. It consists in a matrix of 0 and 1 that represents the pair in a finite set. More information on section

3.3.2 and https://en.wikipedia.org/wiki/Logical_matrix

The simulations were performed on a personal computer using Matlab without an y particular optimisation of algorithm 1.

Acknowledgements

ACKNOWLEDGEMENTS

particular Florian (both of them), Pius, Christelle, Hanane, Caroline and Arthur.

I would like to thank Franco Bagnoli and Duccio Fanelli for welcoming me to

CHAPTER 4

Synchronisation as State Estimator

RÉSUMÉ

Dans ce chapitre, nous présenterons la synchronisation des AC et nous l'étudierons comme un estimateur d'état. Cette approche est sensiblement différente de celles présentées au chapitre précédent, car la bonne reconstruction de l'état par l'estimateur n'est pas caractérisée par l'observabilité ou la reconstructibilité, mais par une étude statistique. Dans un premier temps, nous présenterons la synchronisation des automates cellulaires de Bagnoli et nous détaillerons en quoi celle-ci est très proche de la formulation d'un estimateur d'état. Ensuite, nous caractériserons la propagation de l'erreur initiale dans les AC élémentaires lorsque l'erreur initiale est faible. Finalement, nous présenterons une nouvelle méthode de synchronisation lorsque l'erreur initiale est faible et nous la comparerons à la précédente.

Contents

• S = {0, 1, 2, 3} The choice of the neighbourhood provides the possibility to change the shape of the fire propagation and consequently to perform a circular propagation as it is the "natural" propagation shape. For their fire propagation model, Karafyllidis and Thanailakis used a Moore neighbourhood with lower coefficients for the angles. While using discrete states, we cannot use this artefact and the fire propagation shapes for the Von Neumann and Moore neighbourhood are far from circular (see Figures 5.5a and 5.5b). For this reason, we decrease the density of the forest. At the initialisation of the forest not all cells will be trees, but some will be empty. The density is defined as the probability for a cell to be initiated as a tree cell. For example, with a density = 0.7 each cell has a probability = 0.7 of being a tree and a probability = 0.3 of being empty. Therefore, by decreasing the density sufficiently, the fire cannot propagate in a straight line (see Figure 5.4). When taking the mean for several fire spreads (or when considering a much larger number of cells), the mean fire front becomes circular. In order to have a circular shape, we use a density = 0.7 for the Von Neumann and a density = 0.5 for the Moore neighbourhoods (see Figures 5.5c and 5.5d). A

Construction of a Robust State Estimator

In this thesis, we have presented the construction of a state estimator. However, the choice in the position of the sensors is not an easy task. It would be necessary to develop methods to automatically place the sensors in such a way as to ensure observability. Adaptability could be used as a condition to do this. The choice of the sensor network and the synthesis of the state estimator must also take into account the error tolerance required for the chosen application.

PERSPECTIVES FOR LONG-TERM RESEARCH

Finally, the long-term objective of this research is the application to a real case. This requires all the steps shown in this thesis, from modelling the system by a cellular automaton, to the realisation of a robust state estimator. All this to allow the monitoring of a complex system with a sensor network using a cellular automaton model. In the case of a physical system, this requires additional specific knowledge, for example in engineering for the construction of sensors.

APPENDIX A

Compared Injectivity

In this appendix we present the notion of compared injectivity, a notion close to classical injectivity. As discussed in section 2.3.3 on page 33, injectivity is to observability what compared injectivity is to reconstructibility. This new notion of injectivity is originally related to the notion of reconstructibility but we have chosen to define it in this appendix to make it independent of the context of the thesis and to allow its use to the widest possible audience.

This appendix is separated in three parts, the first one presents formally the definition of compared injectivity, the second presents different properties, and the last one proposes a method to verify the compared injectivity when considering linear algebra.

In order not to confuse the term injectivity with compared injectivity, we will use the term usual injectivity to refer to the classical definition of injectivity. First, we will define some notations that we will use throughout this appendix: Directly, we establish that the usual injectivity can be defined as an injectivity with respect to the identity . Moreover, this new formulation allows to formulate an injection between the two codomains, where each element of ( ) is associated with a single element of ( ) as on the Figure A.1. The compared injectivity can thus be expressed as follows: ∀ ∈ ( ), ∃! ∈ , ∃ ∈ , = ( ) and = ( )

A.2 PROPERTIES OF COMPARED INJECTIVITY

Several properties exist concerning compared injectivity, notably the transitivity property when one of the two functions is usually injective.

Proposition A.1 (Transitivity).

If is injective with respect to and is injective with respect to ℎ, then is injective with respect to ℎ.

Proof. Consider the applications : → , : → and ℎ : → . Since is injective with respect to and with respect to ℎ then the following two statements are true.

Immediately, it is clear that:

We can conclude that is injective with respect to ℎ. Proposition A.2. If is usually injective, then is injective with respect to every applications .

Proof. Consider the applications : → and : → . If is usually injective, then is injective with respect to . Moreover, the following statement is true for all ∈ :

Therefore, is injective with respect to every application ∈ .

Proposition A.3. If is injective with respect to and is usually injective, then is usually injective.

Proof. Consider the applications : → and : → . If is usually injective, then is injective with respect to . Using the transitivity property (proposition A.1), if is injective with respect to then is injective with respect to , therefore is usually injective.

A.3 COMPARED INJECTIVITY IN LINEAR ALGEBRA

When we consider that the functions and are linear applications, it is possible to check the comparative injectivity more easily.

Proposition A.4. Let and be the matrix of the two linear map and . is injective with respect to if and only if :

ker ⊂ ker Proof. Consider the matrices and of the applications : → and : → . Suppose that is injective with respect to , then :

APPENDIX B

Semi-Tensor Product

In this appendix, we will present in detail the construction of the logic matrix which describes the dynamics of the Boolean network. We will start by presenting some properties of the Semi-Tensor Product (STP) before applying this method to the BN presented in chapter 3, the example is presented below in Figure B.1.

B.1 PROPERTIES OF THE SEMI-TENSOR PRODUCT

We present here three properties described by [START_REF] Cheng | Semi-tensor product of matrices and its applications to dynamic systems[END_REF] that will be useful for the construction of the matrix . The first two will be used as a pseudo-commutativity and the last one will be used to reduce the exponent of a boolean variable.

Remark B.1.

It is important to note that the matrices described by Cheng et al in their articles are different from ours because of the changes we made as presented as remark 3.2.

The STP has a pseudo-commutativity property when one of the two elements is a vector, this will allow us to isolate the elements of the vector from the elements of the matrix . It is defined as: Proposition B.1. Assume ∈ × is given. Let be a column vector of size . Then

Next, we define swap matrices, they will be used to have a pseudo commutativity between two vectors. They are defined as: Definition B.1 (Swap Matrices). The swap matrix [ , ] is an × matrix. Its columns are labelled by (11, 12, . . . , 1 , . . . , 1, 2, . . . , ) and its rows by (11, 21, . . . , 1, . . . , 1 , 2 , . . . , ). Then the element in the position (( , ), ( , )) is defined by: ( ),( ) = 0, = and = 1, otherwise

B-1

From this matrix, we can the proposition that allows us to invert two vectors and .

Proposition B.2. Let and be two column vectors respectively of size and .

To calculate , we will need a reduction matrix which will reduce the exponents of the matrix = 2 . They are defined as :

More generally, Cheng proposes in (Cheng and Qi, 2010, theorem IV.6) to construct the matrix of the system (B.4) in a systematic way with the equation (B.5).

where Φ is defined by :

In the next section, we will calculate the matrix from the BN shown in

B.2 DETAILED EXAMPLE ON A SIMPLE BOOLEAN NETWORK

In this section, we will give an example of how we can calculate from the Boolean expressions of the BN. We will use the example presented in chapter 3, it is described in First, we will calculate the matrices , and . This is expressed from the logic matrices of the elementary operators which correspond to their truth tables. = not = 0 1 1 0

= and = 1 1 1 0 0 0 0 1

From the definition of = we can write that :

Once the part of the logical matrices is isolated, we can be interested in grouping under the form so as to be able to express +1 in function of .

Finally we have that the matrix is defined by :