deleted 11 characters in body
Source Link
D.W.
  • 135.4k
  • 18
  • 182
  • 389

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

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.

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.

added 112 characters in body
Source Link
D.W.
  • 135.4k
  • 18
  • 182
  • 389

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.

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

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

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.

Source Link
D.W.
  • 135.4k
  • 18
  • 182
  • 389

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

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