Lagmental Vicfred

Semirings Explain Why One Graph Recurrence Solves Many Problems by Vicfred

tags: mathematics, dynamic programming, semirings, state spaces

Changing addition and multiplication in a path algebra changes what a matrix product aggregates. The formulas are more useful when each symbol has a job rather than merely decorating the theorem.

Start locally

A full dynamic-programming state \(dp[i][s]\) states exactly which prefix \(i\) and mathematical state \(s\) have been processed. The recurrence is a theorem about transitions between these states.

$$ (A\otimes B)_{ij}=\bigoplus_kA_{ik}\odot B_{kj} $$

There are two layers here: the object \(\mathsf D\) and the law \(\mathsf C\). Writing them separately makes the direction of \(\Longrightarrow\) visible and keeps an accidental converse from slipping in.

$$ \text{path value}=\bigoplus_{P:i\rightsquigarrow j}\ \bigodot_{e\in P}w(e) $$

Compute before generalising

An explicit case prevents the notation from becoming ceremonial. Every subscript and superscript in the display contributes to the value.

$$ \begin{array}{c|cc}\text{problem}&\oplus&\odot\\\hline\text{reachability}&\lor&\land\\\text{shortest path}&\min&+\\\text{path counting}&+&\times\end{array} $$

The global view

The two-row display is also a debugging tool: if the conclusion changes when only notation changes, some hidden choice has entered the argument.

$$ \begin{aligned} \mathsf{D}\;&:\quad (A\otimes B)_{ij}=\bigoplus_kA_{ik}\odot B_{kj},\\[5pt] \mathsf{C}\;&:\quad \text{path value}=\bigoplus_{P:i\rightsquigarrow j}\ \bigodot_{e\in P}w(e). \end{aligned} $$

Edge conditions

State compression is an implementation change, not the definition. Loop order is safe only after the uncompressed dependency graph is understood.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \text{path value}=\bigoplus_{P:i\rightsquigarrow j}\ \bigodot_{e\in P}w(e) \end{gathered}} $$

The important habit is to remember what was fixed before the calculation began and what was proved only afterward. The final display preserves that order.

This article was posted on Sat 26 June 2010. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.