Reformulation and Equivalence of Bock's Algorithm for Exact Dependency Parsing
Organizations: UBC Canada · KAIST South Korea
Abstract
Bock's algorithm provides a matrix-based alternative to Chu--Liu/Edmonds (CL/E) for exact dependency parsing. We present a reformulation that retains original node and arc identities through component labels, column adjustments, and star-and-bar transfers. In exact arithmetic, we prove operational equivalence to original Bock under matching scan and tie rules, and establish correspondence with corrected Tarjan under a prescribed component schedule. A separate analysis establishes optimal-value equivalence with Dozat-derived CL/E under the stated score and single-root conventions. We integrate reformulated Bock into a biaffine dependency parser and evaluate decoding and structured training on the Penn Treebank and Chinese Treebank. These results establish Bock as an alternative exact oracle for dependency parsing and structured training, while distinguishing equality of optimal values from identity of returned trees and training trajectories.
Figures & tables
| PTB | CTB | |||||
|---|---|---|---|---|---|---|
| Training | UAS | LAS | LCM | UAS | LAS | LCM |
| Local CE | ||||||
| Hinge (CL/E) | ||||||
| Hinge (Bock) | ||||||
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
| Symbol | Role in Bock’s procedure |
|---|---|
| Amount subtracted from the costs of links entering . The adjusted cost of is ; the procedure changes when the span containing is adjusted. | |
| Head of the link currently starred into . Thus, means that is provisionally selected, whereas means that no link is starred into . | |
| Arc reference used by the star-and-bar transfer. In a nonempty pair, is the referenced link’s head and its dependent; need not equal . A backward trace writes its candidate into an empty entry, and L10 may subsequently redirect that reference to a displaced link. If a star entering is displaced, the entry read at supplies the next candidate. The pair denotes an empty entry. | |
| Label of the span currently containing . Equal positive labels identify nodes represented as one contracted span; a negative label temporarily marks a span encountered during the backward trace. |
Dependency Parsing
Dependency parsing identifies grammatical relationships between words and represents sentence structure as a tree.
See all 25 papers