Efficient Outside Computation Article Swipe

PDF

Related Concepts

Computation Parsing Semiring Variety (cybernetics) Computer science Function (biology) Value (mathematics) Algorithm Composition (language) Theoretical computer science Mathematics Algebra over a field Mathematical optimization Artificial intelligence Discrete mathematics Pure mathematics Machine learning Linguistics Philosophy Biology Evolutionary biology

Daniel Gildea ·

YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.1162/coli_a_00386 · OA: W3094446004

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 out-side 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.