cs.CLMar 29, 2026

A tree interpretation of arc standard dependency derivation

Authors: Zihao Huang, Ai Ka Lee, Jungyeul Park

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Arc-standard derivations over projective dependency trees can be interpreted as the incremental construction of lexicalized ordered trees with contiguous yields. Each shift, leftarc, and rightarc transition corresponds to a deterministic tree update, and the resulting ordered tree uniquely determines the dependency arcs introduced by the derivation. We show that this representation is not an arbitrary encoding: a single-headed dependency tree admits such a contiguous ordered representation if and only if it is projective. The proposal is therefore derivational rather than conversion-based, since the ordered object is defined over the transition sequence itself rather than obtained by transforming a completed dependency graph. This gives a tree-theoretic interpretation of arc-standard parsing, in which projective dependency derivations implicitly construct recoverable constituency-style ordered trees. For non-projective inputs, the interpretation can be used through pseudo-projective lifting and inverse decoding. A small implementation study confirms that the mapped derivations are executable in an existing neural transition-based parser.

Figures & tables

Figure 1: A dependency graph and its ordered dependency tree representation. In the dependency graph, book is the head of the iobj and dobj dependents, while flight is the head of the det and compound dependents.
DatasetUASLAS
PTB–WSJ95.9494.90
Table 1: Dependency recovery from predicted ordered trees on PTB–WSJ.
Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

StepStackBufferActionRelation added
0[root][book, me, the, morning, flight]shift 
1[root, tbookt_{\text{book}} ][me, the, morning, flight]shift 
2[root, tbookt_{\text{book}} , tmet_{\text{me}} ][the, morning, flight]rightarcbook →\rightarrow me
3[root, tbook′t^{\prime}_{\text{book}} ][the, morning, flight]shift 
4[root, tbook′t^{\prime}_{\text{book}} , tthet_{\text{the}} ][morning, flight]shift 
5[root, tbook′t^{\prime}_{\text{book}} , tthet_{\text{the}} , tmorningt_{\text{morning}} ][flight]shift 
Appendix
Table 2: Arc-standard transition sequence and stack evolution for the running example.
Figure 2: Representative snapshots of the ordered tree obtained after selected steps of the transition sequence in Table 2 .
More in this topic

Dependency Parsing

Dependency parsing identifies grammatical relationships between words and represents sentence structure as a tree.

See all 24 papers

Explore similar work

CardsList
Apr 6, 2026

Formal Constraints on Dependency Syntax

Dependency syntax represents the structure of a sentence as a tree composed of dependencies, i.e., directed relations between lexical units. While in its more general form any such tree is allowed, in practice many are not plausible or are very infrequent in attested language. This has motivated a search for constraints characterizing subsets of trees that better fit real linguistic phenomena, providing a more accurate linguistic description, faster parsing or insights on language evolution and human processing. Projectivity is the most well-studied such constraint, but it has been shown to be too restrictive to represent some linguistic phenomena, especially in flexible-word-order languages. Thus, a variety of constraints have been proposed to seek a realistic middle ground between the limitations of projectivity and the excessive leniency of unrestricted dependency structures.

Gómez-Rodríguez, Carlos, Alemany-Puig +1

Universidade da Coru˜na, CITIC, Departamento de Ciencias de la Computación y Tecnologías de la Información, Campus de Elvi˜na, s/n, 15071 A Coruña, Spain · Universitat Politècnica de Catalunya, Departament de Ciències de la Computació, Campus Nord, 1–3, 08034 Barcelona, Spain

Dependency Parsing
AskPDF
May 27, 2026

Better heads do not guarantee better binarized constituency parsing

We revisit punctuation-aware tree binarization for constituency parsing and ask whether dependency-induced headedness improves binary parser supervision. Although learned heads substantially outperform rule-based heads in intrinsic head prediction, they do not yield consistent parsing gains after debinarization. In particular, punctuation-conditioned evaluation shows that learned headedness underperforms rule-based binarization in macro-average punctuation-sensitive F1F_1, despite a small overall gain on CTB. Similar instability appears under cross-treebank transfer. These results suggest that \ycc{linguistically grounded} headedness is not necessarily parser-optimal when used as a binarization control signal. The paper presents a negative result: better head prediction does not imply better punctuation-sensitive constituency parsing.

Zeyao Qi, Yige Chen, Eitan Klinger +2

The Chinese University of Hong Kong, Ma Liu Shui, Hong Kong · The University of British Columbia, Vancouver, Canada · Korea Advanced Institute of Science & Technology, Daejeon, South Korea

Constituency Parsing
AskPDF
Mar 16, 2026

Learning Constituent Headedness

Headedness is widely used as an organizing device in syntactic analysis, yet constituency treebanks rarely encode it explicitly and most processing pipelines recover it procedurally via percolation rules. We treat this notion of constituent headedness as an explicit representational layer and learn it as a supervised prediction task over aligned constituency and dependency annotations, inducing supervision by defining each constituent head as the dependency span head. On aligned English and Chinese data, the resulting models achieve near-ceiling intrinsic accuracy and substantially outperform Collins-style rule-based percolation. Predicted heads yield comparable parsing accuracy under head-driven binarization, consistent with the induced binary training targets being largely equivalent across head choices, while increasing the fidelity of deterministic constituency-to-dependency conversion and transferring across resources and languages under simple label-mapping interfaces.

Zeyao Qi, Yige Chen, KyungTae Lim +2

The Chinese University of Hong Kong · Korea Advanced Institute of Science & Technology

Constituency ParsingStructured Prediction
AskPDF