Axiomatization of Restricted Non-Projective Dependency Trees through Finite-State Constraints that Analyse Crossing Bracketings
Anssi Yli-Jyrä · 2004
In this paper, a representation for syntactic dependency trees (D-trees) is defined through a finite set of axioms. The axiomatized representation constitutes a string that can encode non-projective D-trees of restricted structural complexity. Upper-bounds for the structural complexity of these D-trees are fixed through the following new parameters: proper embracement depth , nested crossing depth ¡ , and non-projectivity depth ¢. In the representation, syntactic dependencies between words are indicated with pairs of brackets. When the brackets indicate dependencies that cross each other, the crossing pairs of brackets are distinguished by assigning separate colors to each of them. These colors are allocated in a way (Yli-Jyrä and Nykänen, 2004) that ensures a unique representation for each D-tree, and entails that languages whose nested crossing depth is not bounded cannot be captured using a fixed number of colors. Although the axiomatization is finite, it ensures that the represented dependency structures are trees. This is possible because the described D-trees have bounded non-projectivity depth. The axioms are also regular because proper embracement depth of represented D-trees is bounded. Our representation suggests that extra strong generative power can be squeezed out of finite-state equivalent grammars. Bracketed D-tree representations (cf. annotated sentences) are structural descriptions that are assigned to their subsequences (cf. generated strings or yields of trees) where brackets and other special-purpose characters have been omitted. 1