Recently, Kuhlmann (2007, Dependency Structures and Lexicalized Grammars. PhD Thesis, Saarland University) and collaborators have shown how the derivations of generative grammars can be recast as dependency structures. This connection between the generative and dependency traditions opens the door to a fresh perspective on how to formally characterize natural language and what minimal machinery can cover such data. This article draws on both reported properties of structures in dependency treebanks and properties of informant data to determine the complexity of natural language along two dependency measures, gap degree (a measure of discontinuity) and well- versus ill-nestedness (whether interleaving substructures are permitted). We show that natural language includes constructions that require dependency analyses that are ill-nested and/or gap degree > 1, and argue that a grammar formalism on the right track for characterizing natural language should be able to generate such structures. We investigate the adequacy of tree-local multi-component tree adjoining grammar (TL-MCTAG) to cover existent data, examining the relationship between TL-MCTAG derivations and dependency representations. Though focused on TL-MCTAG, this work also advances the larger enterprise of discovering mathematically defined formal systems and testing their adequacies by using both linguistic judgments as well as large bodies of data from annotated corpora.