First European Conference on Speech Communication and Technology

Paris, France
September 27-29, 1989

A Chart Parsing Realisation of Dynamic Programming, with Best-First Enumeration of Paths in a Lattice

Henry S. Thompson

Department of Artificial Intelligence, Centre for Cognitive Science, Centre for Speech Technology Research, University of Edinburgh, Edinburgh, Scotland, UK

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.

Full Paper

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.