Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing

Anssi Yli-Jyrä, Carlos Gómez-Rodríguez


Abstract
We present a simple encoding for unlabeled noncrossing graphs and show how its latent counterpart helps us to represent several families of directed and undirected graphs used in syntactic and semantic parsing of natural language as context-free languages. The families are separated purely on the basis of forbidden patterns in latent encoding, eliminating the need to differentiate the families of non-crossing graphs in inference algorithms: one algorithm works for all when the search space can be controlled in parser input.
Anthology ID:
P17-1160
Volume:
Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
Month:
July
Year:
2017
Address:
Vancouver, Canada
Editors:
Regina Barzilay, Min-Yen Kan
Venue:
ACL
SIG:
Publisher:
Association for Computational Linguistics
Note:
Pages:
1745–1755
Language:
URL:
https://aclanthology.org/P17-1160
DOI:
10.18653/v1/P17-1160
Bibkey:
Cite (ACL):
Anssi Yli-Jyrä and Carlos Gómez-Rodríguez. 2017. Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1745–1755, Vancouver, Canada. Association for Computational Linguistics.
Cite (Informal):
Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing (Yli-Jyrä & Gómez-Rodríguez, ACL 2017)
Copy Citation:
PDF:
https://aclanthology.org/P17-1160.pdf
Poster:
 P17-1160.Poster.pdf
Software:
 P17-1160.Software.zip
Code
 amikael/ncdigraphs