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.
Cite as: Thompson, H.S. (1989) A chart parsing realisation of dynamic programming, with best-first enumeration of paths in a lattice. Proc. First European Conference on Speech Communication and Technology (Eurospeech 1989), 1378-1381, doi: 10.21437/Eurospeech.1989-111
@inproceedings{thompson89_eurospeech,
author={Henry S. Thompson},
title={{A chart parsing realisation of dynamic programming, with best-first enumeration of paths in a lattice}},
year=1989,
booktitle={Proc. First European Conference on Speech Communication and Technology (Eurospeech 1989)},
pages={1378--1381},
doi={10.21437/Eurospeech.1989-111}
}