Cache Transition Systems for Graph Parsing

Daniel Gildea, Giorgio Satta, Xiaochang Peng


Abstract
Motivated by the task of semantic parsing, we describe a transition system that generalizes standard transition-based dependency parsing techniques to generate a graph rather than a tree. Our system includes a cache with fixed size m, and we characterize the relationship between the parameter m and the class of graphs that can be produced through the graph-theoretic concept of tree decomposition. We find empirically that small cache sizes cover a high percentage of sentences in existing semantic corpora.
Anthology ID:
J18-1004
Volume:
Computational Linguistics, Volume 44, Issue 1 - April 2018
Month:
April
Year:
2018
Address:
Cambridge, MA
Venue:
CL
SIG:
Publisher:
MIT Press
Note:
Pages:
85–118
Language:
URL:
https://aclanthology.org/J18-1004
DOI:
10.1162/COLI_a_00308
Bibkey:
Cite (ACL):
Daniel Gildea, Giorgio Satta, and Xiaochang Peng. 2018. Cache Transition Systems for Graph Parsing. Computational Linguistics, 44(1):85–118.
Cite (Informal):
Cache Transition Systems for Graph Parsing (Gildea et al., CL 2018)
Copy Citation:
PDF:
https://aclanthology.org/J18-1004.pdf