Dynamic programming by polymorphic semiring algebraic shortcut fusion

Dynamic programming (DP) is an algorithmic design paradigm for the efficient,exact solution of otherwise intractable, combinatorial problems. However, DPalgorithm design is often presented in an ad-hoc manner. It is sometimesdifficult to justify algorithm correctness. To address this issue, this paperpresents a rigorous algebraic formalism for systematically deriving DPalgorithms, based on semiring polymorphism. We start with a specification,construct an algorithm to compute the required solution which is self-evidentlycorrect because it exhaustively generates and evaluates all possible solutionsmeeting the specification. We then derive, through the use of shortcut fusion,an implementation of this algorithm which is both efficient and correct. Wealso demonstrate how, with the use of semiring lifting, the specification canbe augmented with combinatorial constraints, showing how these constraints canbe fused with the algorithm. We furthermore demonstrate how existing DPalgorithms for a given combinatorial problem can be abstracted from theiroriginal context and re-purposed. This approach can be applied to the full scope of combinatorial problemsexpressible in terms of semirings. This includes, for example: optimalprobability and Viterbi decoding, probabilistic marginalization, logicalinference, fuzzy sets, differentiable softmax, relational and provenancequeries. The approach, building on ideas from the existing literature onconstructive algorithmics, exploits generic properties of polymorphicfunctions, tupling and formal sums and algebraic simplifications arising fromconstraint algebras. We demonstrate the effectiveness of this formalism forsome example applications arising in signal processing, bioinformatics andreliability engineering. Python software implementing these algorithms can bedownloaded from: http://www.maxlittle.net/software/dppolyalg.zip.