Search papers, labs, and topics across Lattice.
This paper revisits and clarifies Bock's 1971 algorithm for finding minimum directed spanning trees (arborescences), crucial for non-projective dependency parsing. It provides a detailed, line-by-line execution trace of Bock's original example and reformulates the algorithm to expose its phase structure, state, and control flow. The paper also demonstrates how to adapt a dependency parsing example from Jurafsky and Martin to Bock's formulation, enhancing the algorithm's accessibility and reproducibility.
Bock's 1971 minimum spanning tree algorithm, a cornerstone for non-projective dependency parsing, gets a modern makeover, making it finally understandable and implementable.
This paper presents a gentle tutorial and a structured reformulation of Bock's 1971 Algol procedure for constructing minimum directed spanning trees. Our aim is to make the original algorithm readable and reproducible for modern readers, while highlighting its relevance as an exact decoder for nonprojective graph based dependency parsing. We restate the minimum arborescence objective in Bock's notation and provide a complete line by line execution trace of the original ten node example, extending the partial trace given in the source paper from initialization to termination. We then introduce a structured reformulation that makes explicit the procedure's phase structure, maintained state, and control flow, while preserving the logic of the original method. As a further illustration, we include a worked example adapted from {jurafsky-martin-2026-book} for dependency parsing, showing how a maximum weight arborescence problem is reduced to Bock's minimum cost formulation by a standard affine transformation and traced under the same state variables.
