Hyperedge replacement and nonprojective dependency structures

Synchronous Hyperedge Replacement Graph Grammars (SHRG) can be used to translate between strings and graphs. In this paper, we study the capacity of these grammars to create non-projective dependency graphs. As an example, we use languages that contain cross serial dependencies. Lexicalized hyperedge replacement grammars can derive string languages (as path graphs) that contain an arbitrary number of these dependencies so that their derivation trees reflect the correct dependency graphs. We find that, in contrast, string-to-graph SHRG that derive dependency structures on the graph side are limited to derivations permitted by the string side. We show that, as a result, string-to-graph SHRG cannot capture languages with an unlimited degree of crossing dependencies. This observation has practical implications for the use of SHRG in semantic parsing.