Solving "pseudo-injective" polynomial equations over finite dynamical systems
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914459722711040 |
|---|---|
| author | Porreca, Antonio E. Rolland, Marius |
| author_facet | Porreca, Antonio E. Rolland, Marius |
| contents | We consider the semiring of abstract finite dynamical systems up to isomorphism, with the operations of alternative and synchronous execution. We continue searching for efficient algorithms for solving polynomial equations of the form $P(X) = B$, with a constant side B, with the goal of decomposing complex behaviors into simpler systems. Taking inspiration from the characterization of injective polynomials P over dynamical systems, which is based on a condition on the lengths of limit cycles of their coefficients, we introduce a more general notion of pseudo-injectivity by relaxing this constraint. We prove that the associated equations can be solved efficiently, even in certain cases where the input is encoded in an exponentially more compact way. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_06986 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Solving "pseudo-injective" polynomial equations over finite dynamical systems Porreca, Antonio E. Rolland, Marius Discrete Mathematics Dynamical Systems We consider the semiring of abstract finite dynamical systems up to isomorphism, with the operations of alternative and synchronous execution. We continue searching for efficient algorithms for solving polynomial equations of the form $P(X) = B$, with a constant side B, with the goal of decomposing complex behaviors into simpler systems. Taking inspiration from the characterization of injective polynomials P over dynamical systems, which is based on a condition on the lengths of limit cycles of their coefficients, we introduce a more general notion of pseudo-injectivity by relaxing this constraint. We prove that the associated equations can be solved efficiently, even in certain cases where the input is encoded in an exponentially more compact way. |
| title | Solving "pseudo-injective" polynomial equations over finite dynamical systems |
| topic | Discrete Mathematics Dynamical Systems |
| url | https://arxiv.org/abs/2504.06986 |