Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing
This work addresses a technical bottleneck in natural language parsing by providing a unified approach for multiple graph families, though it appears incremental as it builds on existing parsing methods.
The authors tackled the problem of representing various families of noncrossing graphs in dependency parsing by introducing a simple encoding and its latent counterpart, which allows these families to be expressed as context-free languages and handled by a single inference algorithm, eliminating the need for separate algorithms for each family.
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.