Efficient Outside Computation

Abstract

Weighted deduction systems provide a framework for
  describing parsing algorithms that can be used with
  a variety of operations for combining the values
  of partial derivations.  For some operations, inside
  values can be computed efficiently, but outside values cannot.
  We view outside values as functions from inside values
  to the total value of all derivations, and
  we analyze outside computation in terms of function composition.
  This viewpoint helps explain why efficient outside computation is
  possible in many settings, despite the lack of a general
  outside algorithm for semiring operations.