Bandeau_logo_GDR_IFM_V_5.png
 
18-21 mars 2024 | Grenoble  (France)
Alpes.jpg
Hypotheses and Equations on Discrete Dynamical Systems
Sara Riva  1  
1 : CRIStAL
Research Centre in Computer Science, Signal and Automatic Control of Lille (CRIStAL UMR 9189)

In biology, as in physics, astronomy, and other fields, we study and model various phenomena using a variety of tools such as Boolean Networks, Cellular Automata, etc. Using some of these models, we find ourselves analyzing Finite Discrete-time Dynamical Systems (DDS). A DDS consists of a finite set X, called state space, and a function f, called next-state map (which associates to a state v the state f(v)). While the mathematical formalization and the results that found up to nowadays are elegant and meaningful, often they are not very suitable in practice because of their high computational cost. In the literature, it is known that DDS equipped with appropriate sum and product operations form a commutative semiring. This algebraic structure allows us to write polynomial equations in which the coefficients and unknowns are DDS. In particular, if we are interested in some dynamics derived from experimental data, we can write an equation with this as a constant right-hand term and model assumptions about the function f (or its properties) in a polynomial left-hand term. Finding solutions to this equation allows us to better understand the phenomenon and its properties. This approach is interesting but it has important limitations from a computational point of view. Solving a polynomial equation (with several variables) is, in general, undecidable, and even if we focus on the case of hypothesis validation, the computational cost remains high. The idea is then to look for approximations that give relevant information about the solutions of the original equation. It is possible to introduce three abstractions (simpler equations) to identify: the number of states of the variables, the asymptotic behavior, or the transient behavior (what happens before the system stabilizes). Each one is built from a theoretical and algorithmic point of view to introduce a method to perform hypothesis validation on DDS. Through algebraic transformations, it is possible to enumerate the solutions of a polynomial equation with a constant term by enumerating a finite number of simpler equations. Finally, the connection between the solution of these simple equations and the cancellation problem, known in graph theory, is explored to study the transient behavior of a system.



  • Poster
Personnes connectées : 1 Vie privée
Chargement...