{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T23:42:56Z","timestamp":1775000576619,"version":"3.50.1"},"reference-count":63,"publisher":"MIT Press - Journals","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2013,6]]},"abstract":"<jats:p> Syntactic representations based on word-to-word dependencies have a long-standing tradition in descriptive linguistics, and receive considerable interest in many applications. Nevertheless, dependency syntax has remained something of an island from a formal point of view. Moreover, most formalisms available for dependency grammar are restricted to projective analyses, and thus not able to support natural accounts of phenomena such as wh-movement and cross\u2013serial dependencies. In this article we present a formalism for non-projective dependency grammar in the framework of linear context-free rewriting systems. A characteristic property of our formalism is a close correspondence between the non-projectivity of the dependency trees admitted by a grammar on the one hand, and the parsing complexity of the grammar on the other. We show that parsing with unrestricted grammars is intractable. We therefore study two constraints on non-projectivity, block-degree and well-nestedness. Jointly, these two constraints define a class of \u201cmildly\u201d non-projective dependency grammars that can be parsed in polynomial time. An evaluation on five dependency treebanks shows that these grammars have a good coverage of empirical data. <\/jats:p>","DOI":"10.1162\/coli_a_00125","type":"journal-article","created":{"date-parts":[[2012,8,22]],"date-time":"2012-08-22T13:28:44Z","timestamp":1345642124000},"page":"355-387","source":"Crossref","is-referenced-by-count":23,"title":["Mildly Non-Projective Dependency Grammar"],"prefix":"10.1162","volume":"39","author":[{"given":"Marco","family":"Kuhlmann","sequence":"first","affiliation":[{"name":"Uppsala University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"R1","volume-title":"The derivational generative power of formal systems, or: Scrambling is beyond LCFRS. IRCS Report 92-38","author":"Becker Tilman","year":"1992"},{"key":"R2","first-page":"66","volume-title":"Proceedings of the Seventh International Workshop on Parsing Technologies (IWPT)","author":"Bertsch Eberhard","year":"2001"},{"key":"R3","first-page":"195","volume-title":"Proceedings of the 10th Conference on Formal Grammar (FG) and Ninth Meeting on Mathematics of Language (MOL)","author":"Bodirsky Manuel","year":"2005"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-010-0201-1_7"},{"key":"R5","volume-title":"Proposal for a natural language processing syntactic backbone.","author":"Boullier Pierre","year":"1998"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/1-4020-2295-6_13"},{"issue":"4","key":"R7","first-page":"613","volume":"13","author":"Bresnan Joan","year":"1982","journal-title":"Linguistic Inquiry"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.3115\/1596276.1596305"},{"key":"R9","first-page":"21","volume-title":"Proceedings of the Fourth Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+)","author":"Candito Marie-H\u00e9l\u00e8ne","year":"1998"},{"key":"R10","first-page":"1031","volume-title":"Proceedings of the 13th National Conference on Artificial Intelligence (AAAI) and Eighth Innovative Applications of Artificial Intelligence Conference (IAAI)","volume":"2","author":"Charniak Eugene","year":"1996"},{"key":"R11","volume-title":"Proceedings of the Tenth International Conference on Tree Adjoining Grammars and Related Formalisms (TAG+)","author":"Chen-Main Joan","year":"2010"},{"key":"R12","first-page":"450","volume-title":"Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Crescenzi Pierluigi","year":"2011"},{"key":"R13","first-page":"1388","volume-title":"Fifth International Conference on Language Resources and Evaluations (LREC)","author":"D\u017eeroski Sa\u0161o","year":"2006"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90232-9"},{"key":"R15","first-page":"769","volume-title":"Proceedings of Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL)","author":"Gildea Daniel","year":"2010"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00060"},{"key":"R17","first-page":"276","volume-title":"Proceedings of Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL)","author":"G\u00f3mez-Rodr\u00edguez Carlos","year":"2010"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.3115\/1620754.1620833"},{"key":"R19","first-page":"985","volume-title":"Proceedings of the Joint Conference of the 47th Annual Meeting of the Association for Computational Linguistics (ACL) and the Fourth International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing (IJCNLP)","author":"G\u00f3mez-Rodr\u00edguez Carlos","year":"2009"},{"issue":"4","key":"R20","first-page":"573","volume":"25","author":"Goodman Joshua","year":"1999","journal-title":"Computational Linguistics"},{"key":"R21","first-page":"110","volume-title":"Proceedings of the International Conference on Arabic Language Resources and Tools","author":"Haji\u010d Jan","year":"2004"},{"key":"R22","first-page":"608","volume-title":"Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Havelka Ji\u0159\u00ed","year":"2007"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.2307\/411934"},{"key":"R24","first-page":"21","volume-title":"Proceedings of the Workshop on Processing of Dependency-Based Grammars","author":"Holan Tom\u00e1\u0161","year":"1998"},{"key":"R25","volume-title":"Language Networks. The New Word Grammar.","author":"Hudson Richard","year":"2007"},{"key":"R26","first-page":"81","volume-title":"Van periferie naar kern.","author":"Huybregts Riny","year":"1984"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6_2"},{"issue":"1","key":"R28","first-page":"78","volume":"75","author":"Kaji Yuichi","year":"1992","journal-title":"IEICE Transactions on Information and Systems"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14846-0"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02737-6_25"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13089-2_29"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.3115\/1609067.1609118"},{"key":"R33","volume-title":"The Mathematics of Language, volume 63 of Studies in Generative Grammar.","author":"Kracht Marcus","year":"2003"},{"key":"R34","first-page":"217","volume-title":"Proceedings of the Second Workshop on Treebanks and Linguistic Theories (TLT)","author":"Kromann Matthias Trautner","year":"2003"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.2200\/S00169ED1V01Y200901HLT002"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.3115\/1273073.1273139"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.3115\/1609067.1609120"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8640.1994.tb00011.x"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.3115\/1699510.1699517"},{"key":"R40","volume-title":"Proceedings of the Tenth International Conference on Tree Adjoining Grammars and Related Formalisms (TAG+)","author":"Maier Wolfgang","year":"2010"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20169-1_11"},{"key":"R42","first-page":"61","volume-title":"Proceedings of the 13th Conference on Formal Grammar (FG)","author":"Maier Wolfgang","year":"2008"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1145\/581771.581774"},{"key":"R44","volume-title":"Dependency Syntax: Theory and Practice.","author":"Mel'\u010duk Igor","year":"1988"},{"key":"R45","first-page":"179","volume-title":"Logical Aspects of Computational Linguistics, Third International Conference, LACL 1998, Selected Papers, volume 2014 of Lecture Notes in Computer Science","author":"Michaelis Jens","year":"1998"},{"key":"R46","unstructured":"Michaelis, Jens. 2001. On Formal Properties of Minimalist Grammars. Ph.D. thesis, Universit\u00e4t Potsdam, Potsdam, Germany."},{"key":"R47","first-page":"915","volume-title":"Proceedings of the Joint Conference on Empirical Methods in Natural Language Processing (EMNLP) and Computational Natural Language Learning (CoNLL)","author":"Nivre Joakim","year":"2007"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-010-0201-1_15"},{"key":"R49","first-page":"167","volume-title":"Recent Trends in Meaning-Text Theory, volume 39 of Studies in Language, Companion Series.","author":"Rambow Owen","year":"1997"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.3115\/981658.981679"},{"key":"R51","first-page":"525","volume-title":"Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Sagot Beno\u00eet","year":"2010"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.3115\/981967.981979"},{"key":"R53","unstructured":"Schabes, Yves. 1990. Mathematical and Computational Aspects of Lexicalized Grammars. Ph.D. thesis, University of Pennsylvania, Philadelphia, PA."},{"key":"R54","doi-asserted-by":"publisher","DOI":"10.3115\/991719.991757"},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90374-B"},{"key":"R56","volume-title":"The Meaning of the Sentence in Its Semantic and Pragmatic Aspects.","author":"Sgall Petr","year":"1986"},{"key":"R57","doi-asserted-by":"publisher","DOI":"10.1007\/BF00630917"},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(95)00035-I"},{"key":"R59","doi-asserted-by":"publisher","DOI":"10.1002\/9781444395037.ch5"},{"key":"R60","volume-title":"\u00c9l\u00e9ments de syntaxe structurale.","author":"Tesni\u00e8re Lucien","year":"1959"},{"key":"R61","doi-asserted-by":"publisher","DOI":"10.3115\/981175.981190"},{"key":"R62","doi-asserted-by":"publisher","DOI":"10.3115\/1072228.1072256"},{"key":"R63","unstructured":"Weir, David J. 1988. Characterizing Mildly Context-Sensitive Grammar Formalisms. Ph.D. thesis, University of Pennsylvania, Philadelphia, PA."}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/COLI_a_00125","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:27:18Z","timestamp":1615584438000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/39\/2\/355-387\/1432"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":63,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["10.1162\/COLI_a_00125"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00125","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6]]}}}