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?


2 Answers 2


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.$$

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 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. International Conference on Functional Programming, ICFP '13.

Daniel J. Lehmann. Algebraic structures for transitive closure. Theoretical Computer Science, vol 4 pp.59--76, 1977.

  • $\begingroup$ Is there any significance in using first a lower-case b and then an uppercase B in the equations? $\endgroup$
    – Matthias
    Sep 2, 2020 at 3:13
  • $\begingroup$ @Matthias, oops, no, it was just sloppiness on my part. Sorry, fixed $\endgroup$
    – D.W.
    Sep 2, 2020 at 3:35

Even for the canonical example of a semiring, $\mathbb N$, solving linear equations is hard; in a sense, NP-hard.

See 0-1 Knapsack Problem, and Integer Knapsack Problem (Papadimitriou and Steiglitz, page 376).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.