So I have come across an issue where it would be very nice to solve systems of linear equations over semirings but I have no clue how to do that. Over a field I would use Gaussian elimination but I'm at a loss of how to find solution spaces to even rings much less semirings. In fact I'm not 100% sure this is decidable. The problem demands that I be able to do this for a wide class of semirings (preferably all) and not just 1 specific kind.Are systems of linear semiring equations decidable? If so what algorithms are known to compute solutions for them?
Solving systems of linear equations over semirings
algorithms;undecidability;linear algebra;algebra
I don't think there's any general algorithm that works for arbitrary semirings.  The requirement to be a semiring doesn't give us a lot to work with.However, if you have a closed semiring, then there are algorithms for solving systems of linear equations over the semiring.Closed semiringsA closed semiring is a semiring with a closure operator, denoted $*$, which satisfies the equation$$a^* = 1 + a \times a^* = 1 + a^* \times a.$$A closed semiring is also known as a star semiring.The intuition is that $a^*$ is intended to be the sum of the infinite series$$1 + a + a^2 + a^3 + \dots$$For instance, the regular languages form a closed semiring under union and concatenation; the $*$ operator is the Kleene star.  The real numbers form a closed semiring under addition and multiplication; the $*$ operator is $a^* = 1/(1-a)$.Systems of linear equations over a closed semiringNow, if you have that kind of structure, then there is an analog of Gaussian elimination.  In particular, if you have a linear system of equations$$Ax+b = x$$where $x$ is a vector of variables over the closed semiring, $b$ is a vector of constants, and $A$ is a matrix of constants, then this has the solution$$X = A^* B.$$The closure operator on matrices takes a bit of work to define, but it can be computed efficiently using an analog of Gaussian elimination.For a careful development of the theory, I recommend the following papers:Stephen Dolan.  Fun with Semirings: A functional pearl on the abuse of linear algebra.  International Conference on Functional Programming, ICFP '13.Daniel J. Lehmann.  Algebraic structures for transitive closure.  Theoretical Computer Science, vol 4 pp.59--76, 1977.