The string-generative capacity of regular dependency languages
Laura Kallmeyer, Paola Monachesi, Gerald M. Penn, Giorgio Satta, Marco Kuhlmann, Mathias Möhl · 2009
This paper contributes to the formal theory of dependency grammar. We apply the classical concept of algebraic recognizability to characterize regular sets of dependency structures, and show how in this framework, two empirically relevant structural restrictions on dependency analyses yield infinite hierarchies of ever more expressive string languages.