On solving basic equations over the semiring of functional digraphs

2024/02/26 by Alberto Dennunzio, Enrico Formenti, Dennunzio, Alberto +5 · 1 citation
Decision Sciences · Computer Science · #Fuzzy and Soft Set Theory #Advanced Graph Theory Research #Constraint Satisfaction and Optimization

paper · pdf · doi:10.48550/arxiv.2402.16923

Abstract

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.

Cited by

• There is no prime functional digraph: Seifert's proof revisited

Related

• Dividing sums of cycles in the semiring of functional digraphs
• Some families of graphs, hypergraphs and digraphs defined by systems of equations
• Functional Graphs of Polynomials over Finite Fields
• Bipartite Graphs as Polynomials, and Polynomials as Bipartite Graphs (with a view towards dividing in ℕ[x], ℕ[x,y])
• Computing Least and Greatest Fixed Points in Absorptive Semirings