0

This paper describes a framework for shortest-path algorithms based on semirings. My question is, why do we need left distributivity of ⊕ (generalized sum) over ⊗ (generalized product) for the algorithms to give correct results.

In other words, why do we need the law:

a ⊗ (b ⊕ c) = (a ⊗ b) ⊕ (a ⊗ c)
skvadrik
  • 101

2 Answers2

0

The simple answer is that the paper is going to discuss algorithms that can be applied to semirings. So something has to satisfy the properties of a semiring if you want to apply them!

Typically, algorithms will make great use of the distributivity laws to manipulate summations; e.g. to invoke the identity

$$ \bigoplus_{i,j} \left( a_i \otimes b_j \right) = \left( \bigoplus_i a_i \right) \otimes \left( \bigoplus_j b_j \right) $$

Frequently, problems that can be phrased in terms of interesting semirings are of the sort where

  • You are assembling smaller things into larger things, represented by $\otimes$
  • You are aggregating things into collections, represented by $\oplus$

The distributivity law is simply expressing that you get the same result whether you do the aggregation before or after doing the combinations.

A common example is that the objects represent collections of paths in a graph. The operation $a \otimes b$ yields the collection you get by concatenating a path from $a$ with a path from $b$ in all possible ways, and the operation $a \oplus b$ means to take the union of the two collections.

  • I understand why right distributivity is needed: when we find shortest paths to certain intermediate node, we rely on the property that, whatever common path suffix we may later append, it won't change the fact that the path prefix found so far is the shortest one. But why left distributivity?.. – skvadrik Jan 24 '18 at 07:26
  • Whether you're more interested in left or right distributivity depends heavily on what algorithm you're using. Some algorithms build paths from the source to the destination so need right distributivity, some build paths in the opposite direction so need left distributivity. – Mjiig Jan 24 '18 at 20:42
0

Eh, it turns out left distributivity is not necessary. The paper says:

Our framework can also be generalized by introducing right and left semirings [28]. A right semiring is an algebraic structure similar to a semiring except that it may lack left distributivity.

skvadrik
  • 101