Dividing sums of cycles in the semiring of functional digraphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915829322350592 |
|---|---|
| author | Bridoux, Florian Crespelle, Christophe Phan, Thi Ha Duong Richard, Adrien |
| author_facet | Bridoux, Florian Crespelle, Christophe Phan, Thi Ha Duong Richard, Adrien |
| contents | Functional digraphs are unlabelled finite digraphs where each vertex has exactly one out-neighbor. They are isomorphic classes of finite discrete-time dynamical systems. Endowed with the direct sum and product, functional digraphs form a semiring with an interesting multiplicative structure. For instance, we do not know if the following division problem can be solved in polynomial time: given two functional digraphs $A$ and $B$, does $A$ divide $B$? That $A$ divides $B$ means that there exists a functional digraph $X$ such that $AX$ is isomorphic to $B$, and many such $X$ can exist. We can thus ask for the number of solutions $X$. In this paper, we focus on the case where $B$ is a sum of cycles (a disjoint union of cycles, corresponding to the limit behavior of finite discrete-time dynamical systems). There is then a naïve sub-exponential algorithm to compute the non-isomorphic solutions $X$, and our main result is an improvement of this algorithm which has the property to be polynomial when $A$ is fixed. It uses a divide-and-conquer technique that should be useful for further developments on the division problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_11943 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Dividing sums of cycles in the semiring of functional digraphs Bridoux, Florian Crespelle, Christophe Phan, Thi Ha Duong Richard, Adrien Combinatorics Discrete Mathematics Functional digraphs are unlabelled finite digraphs where each vertex has exactly one out-neighbor. They are isomorphic classes of finite discrete-time dynamical systems. Endowed with the direct sum and product, functional digraphs form a semiring with an interesting multiplicative structure. For instance, we do not know if the following division problem can be solved in polynomial time: given two functional digraphs $A$ and $B$, does $A$ divide $B$? That $A$ divides $B$ means that there exists a functional digraph $X$ such that $AX$ is isomorphic to $B$, and many such $X$ can exist. We can thus ask for the number of solutions $X$. In this paper, we focus on the case where $B$ is a sum of cycles (a disjoint union of cycles, corresponding to the limit behavior of finite discrete-time dynamical systems). There is then a naïve sub-exponential algorithm to compute the non-isomorphic solutions $X$, and our main result is an improvement of this algorithm which has the property to be polynomial when $A$ is fixed. It uses a divide-and-conquer technique that should be useful for further developments on the division problem. |
| title | Dividing sums of cycles in the semiring of functional digraphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2504.11943 |