Roots in the semiring of finite deterministic dynamical systems
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912218069598208 |
|---|---|
| author | Doré, François Perrot, Kévin Porreca, Antonio E. Riva, Sara Rolland, Marius |
| author_facet | Doré, François Perrot, Kévin Porreca, Antonio E. Riva, Sara Rolland, Marius |
| contents | Finite discrete-time dynamical systems (FDDS) model phenomena that evolve deterministically in discrete time. It is possible to define sum and product operations on these systems (disjoint union and direct product, respectively) giving a commutative semiring. This algebraic structure led to several works employing polynomial equations to model hypotheses on phenomena modelled using FDDS. To solve these equations, algorithms for performing the division and computing $k$-th roots are needed. In this paper, we propose two polynomial algorithms for these tasks, under the condition that the result is a connected FDDS. This ultimately leads to an efficient solution to equations of the type $AX^k=B$ for connected $X$. These results are some of the important final steps for solving more general polynomial equations on FDDS. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_09236 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Roots in the semiring of finite deterministic dynamical systems Doré, François Perrot, Kévin Porreca, Antonio E. Riva, Sara Rolland, Marius Discrete Mathematics Dynamical Systems Finite discrete-time dynamical systems (FDDS) model phenomena that evolve deterministically in discrete time. It is possible to define sum and product operations on these systems (disjoint union and direct product, respectively) giving a commutative semiring. This algebraic structure led to several works employing polynomial equations to model hypotheses on phenomena modelled using FDDS. To solve these equations, algorithms for performing the division and computing $k$-th roots are needed. In this paper, we propose two polynomial algorithms for these tasks, under the condition that the result is a connected FDDS. This ultimately leads to an efficient solution to equations of the type $AX^k=B$ for connected $X$. These results are some of the important final steps for solving more general polynomial equations on FDDS. |
| title | Roots in the semiring of finite deterministic dynamical systems |
| topic | Discrete Mathematics Dynamical Systems |
| url | https://arxiv.org/abs/2405.09236 |