Complexity of Dependency Representations for Natural Languages

摘要

Most of the formal issues about the complexity of dependency representations are studied via various types of phrase structure grammars and their capabilities for representing dependencies. We will consider a particular kind of phrase structure grammar, well suited to describe various levels of complexity in the context of dependencies. We will relate these representations to some key linguistic issues and the corresponding parsing complexities. We hope mat this work will give some further insight into the limits of dependency representations as well as the associated processing complexities.