On solving basic equations over the semiring of functional digraphs
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_ | 1866914170373406720 |
|---|---|
| author | Dennunzio, Alberto Formenti, Enrico Margara, Luciano Riva, Sara |
| author_facet | Dennunzio, Alberto Formenti, Enrico Margara, Luciano Riva, Sara |
| contents | Endowing the set of functional graphs (FGs) with the sum (disjoint union of graphs) and product (standard direct product on graphs) operations induces on FGs a structure of a commutative semiring R. The operations on R can be naturally extended to the set of univariate polynomials R[X] over R. This paper provides a polynomial time algorithm for deciding if equations of the type AX=B have solutions when A is just a single cycle and B a set of cycles of identical size. We also prove a similar complexity result for some variants of the previous equation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_16923 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On solving basic equations over the semiring of functional digraphs Dennunzio, Alberto Formenti, Enrico Margara, Luciano Riva, Sara Discrete Mathematics Combinatorics 68R01, 68R010 Endowing the set of functional graphs (FGs) with the sum (disjoint union of graphs) and product (standard direct product on graphs) operations induces on FGs a structure of a commutative semiring R. The operations on R can be naturally extended to the set of univariate polynomials R[X] over R. This paper provides a polynomial time algorithm for deciding if equations of the type AX=B have solutions when A is just a single cycle and B a set of cycles of identical size. We also prove a similar complexity result for some variants of the previous equation. |
| title | On solving basic equations over the semiring of functional digraphs |
| topic | Discrete Mathematics Combinatorics 68R01, 68R010 |
| url | https://arxiv.org/abs/2402.16923 |