Algorithmic reconstruction of discrete dynamics
share
Functional graphs (FG) allow to model under graph structures the behavior of mapping functions from a discrete set to itself. These functions are used to study real complex phenomena evolving in time. As the systems studied can be large, it can be interesting to decompose and factorise them into several sub-graphs acting together. Polynomial equations over functional graphs can help to define in a formal way this decomposition and factorisation mechanism, and solving them validates or invalidates our hypotheses on their decomposability. The current solution methods breaks done the main equation in a series of basic equations of the form A x X=B, with A, X, and B being FG, but they focus only on the cyclic nodes without taking into account the transient one. In this work, we propose an algorithm which solves these basic equations including also this behavior for FG. We exploit a connection with the cancellation problem over the direct product of digraphs to introduce a first upper bound to the number of solutions for these equations. Then, we introduce a polynomial algorithm able to give some information about the dynamics of all the solutions, and a second exponential version able to concretely find all solutions X for a basic equation. The goal is to make a step forward in the analysis of finite but complex functions such as those used in biological regulatory networks or in systems biology.
READ FULL TEXT