A Right-to-Left Chart Parsing for Dependency Grammar using Headable Paths

In this paper, we propose a right-to-left dependency grammar parsing method for languages in which a governor appears after its modifier like Korean and Japanese. Unlike conventional left-to-right parsers, this parsing method can take advantage of the governor post-positioning property of such languages to reduce the size of search space by using the idea of a headable path. A headable path is a path which contains all candidate words which can be the governor of an input word during parsing. A preliminary experiment showed very promising results in reducing the number of intermediate dependency structures and actual parsing time. 1: Introduction The degrees of freedom in word-order vary with each language. Languages like English, French or Chinese are relatively fixed word-order languages, while languages like German are less fixed ones. On the other hand, languages like Korean, Japanese, Russian or Finish are relatively free word-order languages[1, 4]. It has been argued that phras..