Computing abstract decorations of parse forests
  using dynamic programming and algebraic power series

Fr\'ed\'eric Tendeau
INRIA-Rocquencourt(*), BP 105, F 78153 Le Chesnay cedex
E-mail: Frederic.Tendeau@inria.fr

Abstract

Algebraic power series provide a very generic parsing paradigm: an
abstract semiring plays the role of the parse forest domain as well as
the role of a decoration domain.  We use the formalism of algebraic
power series over non-commuting variables to show how to apply dynamic
programming techniques to compute decorations in an abstract semiring,
i.e. without specializing for a particular interpretation such as
booleans (for recognition), forests (for parsing), or any decoration
domain with more practical purposes, such as probabilities or a
variety of feature structures for computational linguistics.

Key words: algebraic power series, dynamic programming, parsing, semiring.

(*) Research partially supported by CNET grant 95-B030.