Cache Transition Systems for Graph Parsing

Abstract

Motivated by the task of semantic parsing, we describe a
  transition system that generalizes standard transition-based
  dependency parsing techniques to generate a graph rather than a
  tree.  Our system includes a cache with fixed size m, and we
  characterize the relationship between the parameter m and the
  class of graphs that can be produced through the
  graph-theoretic concept of tree decomposition.  We find
  empirically that over 99% of Abstract Meaning Representation
  (AMR) graphs can be built with a cache size of seven, and the
  average cache size needed is 2.80.