Paper: A Transition-Based Parser for 2-Planar Dependency Structures

ACL ID P10-1151
Title A Transition-Based Parser for 2-Planar Dependency Structures
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2010
Authors

Finding a class of structures that is rich enough for adequate linguistic represen- tation yet restricted enough for efficient computational processing is an important problem for dependency parsing. In this paper, we present a transition system for 2-planar dependency trees – trees that can be decomposed into at most two planar graphs – and show that it can be used to implement a classifier-based parser that runs in linear time and outperforms a state- of-the-art transition-based parser on four data sets from the CoNLL-X shared task. In addition, we present an efficient method for determining whether an arbitrary tree is 2-planar and show that 99% or more of the trees in existing treebanks are 2-planar.