arXiv cs.CL· Yuxi Wang, Jungyeul Park·· 11 小时前AI 评分18
Bock 算法用于精确依存句法分析的重新表述与等价性证明
Reformulation and Equivalence of Bock's Algorithm for Exact Dependency Parsing
AI 导读
研究提出 Bock 算法的一种重新表述，通过组件标签、列调整与 star-and-bar 变换保留原始节点和弧的身份，并证明在匹配扫描与平局规则下与原 Bock 算法操作等价，且在指定组件调度下与修正版 Tarjan 对应。
正文 · 原文
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.
| Subjects: | Computation and Language (cs.CL) |
| Cite as: | arXiv:2611.00939 [cs.CL] |
| (or arXiv:2611.00939v1 [cs.CL] for this version) | |
| https://doi.org/10.48550/arXiv.2611.00939 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Jungyeul Park [view email]
[v1]
Sat, 31 Oct 2026 13:40:25 UTC (33 KB)
来源：arXiv cs.CL · arxiv.org