patternMinor
Solving systems of linear equations over semirings
Viewed 0 times
solvinglinearequationssystemssemiringsover
Problem
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?
Are systems of linear semiring equations decidable? If so what algorithms are known to compute solutions for them?
Solution
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.
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.
Context
StackExchange Computer Science Q#54616, answer score: 8
Revisions (0)
No revisions yet.