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.
翻译:功能图形( FG) 允许在图形结构下建模从一个离散的设置到它本身的映射函数的行为。 这些功能被用来研究在时间上演进的真正复杂的现象。 由于所研究的系统可能规模巨大, 将它们分解并分解成几个子图, 将它们纳入到几个子图中是很有趣的。 功能图形的多元等式可以帮助以正式的方式定义这种分解和分解机制, 并解决它们, 从而验证或否定我们关于它们分解的假设。 目前的解决办法方法打破了表A X=B( A、 X)和B( B)为FG)的一系列基本方程式中的主方程式。 但是它们只关注周期节点, 而没有考虑到瞬时的一个子。 在这项工作中, 我们建议一种算法, 解决这些基本方程式, 包括FG的这种动作。 我们利用对分数直接产的取消问题, 以引入这些方程式的首个上限。 然后, 我们引入一个多位算法的等式等方程式, 能够提供一些关于模型的动态的动态模型, 也就是的模型的模型, 用于所有的系统。