Active chart parsing offers a clean and flexible way of implementing dynamic programming to find the best path through a-cyclic directed lattices. This paper describes how this comes about and what the general form of a chart parsing realisation of dynamic programming takes. Advantage is taken of the resulting flexibility to produce a system which not only finds the best path, but enumerates paths in order. Finally we exemplify the process for finding paths through a word lattice given bi-class probabilities, and gives a few results from some experiments.
Bibliographic reference. Thompson, Henry S. (1989): "A chart parsing realisation of dynamic programming, with best-first enumeration of paths in a lattice", In EUROSPEECH-1989, 1378-1381.