Report
On solving basic equations over the semiring of functional digraphs
| العنوان: | On solving basic equations over the semiring of functional digraphs |
|---|---|
| المؤلفون: | Dennunzio, Alberto, Formenti, Enrico, Margara, Luciano, Riva, Sara |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Discrete Mathematics, 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. Comment: changed style file |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2402.16923 |
| رقم الانضمام: | edsarx.2402.16923 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |