ISCA Archive Eurospeech 1989
ISCA Archive Eurospeech 1989

A chart parsing realisation of dynamic programming, with best-first enumeration of paths in a lattice

Henry S. Thompson

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.