  In this paper, we propose an algebraic formalization of the two important
classes of dynamic programming algorithms called forward and forward-backward
algorithms. They are generalized extensively in this study so that a wide range
of other existing algorithms is subsumed. Forward algorithms generalized in
this study subsume the ordinary forward algorithm on trellises for sequence
labeling, the inside algorithm on derivation forests for CYK parsing, a
unidirectional message passing on acyclic factor graphs, the forward mode of
automatic differentiation on computation graphs with addition and
multiplication, and so on. In addition, we reveal algebraic structures
underlying complicated computation with forward algorithms. By the aid of the
revealed algebraic structures, we also propose a systematic framework to design
complicated variants of forward algorithms. Forward-backward algorithms
generalized in this study subsume the ordinary forward-backward algorithm on
trellises for sequence labeling, the inside-outside algorithm on derivation
forests for CYK parsing, the sum-product algorithm on acyclic factor graphs,
the reverse mode of automatic differentiation (a.k.a. back propagation) on
computation graphs with addition and multiplication, and so on. We also propose
an algebraic characterization of what can be computed by forward-backward
algorithms and elucidate the relationship between forward and forward-backward
algorithms.
