On solving basic equations over the semiring of functional digraphs
<|reference_start|>On solving basic equations over the semiring of functional digraphs: 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.<|reference_end|>
@article{dennunzio2024on,
    title={On solving basic equations over the semiring of functional digraphs},
    author={Alberto Dennunzio and Enrico Formenti and Luciano Margara and Sara
  Riva},
    journal={arXiv preprint arXiv:2402.16923},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.16923},
    primaryClass={cs.DM math.CO}
}