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 semirings ================ A closed semiring is a semiring with a closure operator, denoted $*$, which satisfies the equation $$a^* = 1 + a \times a^* = 1 + a^* \times a.$$ 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 semiring ================================================== Now, 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](http://www.cl.cam.ac.uk/%7Esd601/papers/semirings.pdf). International Conference on Functional Programming, ICFP '13. Daniel J. Lehmann. [Algebraic structures for transitive closure](http://www.sciencedirect.com/science/article/pii/0304397577900561/pdf?md5=54d77d786ce7532bbd9d93d61b5886e6&pid=1-s2.0-0304397577900561-main.pdf). Theoretical Computer Science, vol 4 pp.59--76, 1977.