{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T20:32:11Z","timestamp":1780950731140,"version":"3.54.1"},"reference-count":76,"publisher":"MIT Press - Journals","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p> Transition-based parsing is a widely used approach for dependency parsing that combines high efficiency with expressive feature models. Many different transition systems have been proposed, often formalized in slightly different frameworks. In this article, we show that a large number of the known systems for projective dependency parsing can be viewed as variants of the same stack-based system with a small set of elementary transitions that can be composed into complex transitions and restricted in different ways. We call these systems divisible transition systems and prove a number of theoretical results about their expressivity and complexity. In particular, we characterize an important subclass called efficient divisible transition systems that parse planar dependency graphs in linear time. We go on to show, first, how this system can be restricted to capture exactly the set of planar dependency trees and, secondly, how the system can be generalized to k-planar trees by making use of multiple stacks. Using the first known efficient test for k-planarity, we investigate the coverage of k-planar trees in available dependency treebanks and find a very good fit for 2-planar trees. We end with an experimental evaluation showing that our 2-planar parser gives significant improvements in parsing accuracy over the corresponding 1-planar and projective parsers for data sets with non-projective dependency trees and performs on a par with the widely used arc-eager pseudo-projective parser. <\/jats:p>","DOI":"10.1162\/coli_a_00150","type":"journal-article","created":{"date-parts":[[2013,1,3]],"date-time":"2013-01-03T17:12:23Z","timestamp":1357233143000},"page":"799-845","source":"Crossref","is-referenced-by-count":18,"title":["Divisible Transition Systems and Multiplanar Dependency Parsing"],"prefix":"10.1162","volume":"39","author":[{"given":"Carlos","family":"G\u00f3mez-Rodr\u00edguez","sequence":"first","affiliation":[{"name":"Universidade da Coru\u00f1a"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joakim","family":"Nivre","sequence":"additional","affiliation":[{"name":"Uppsala University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"281","reference":[{"key":"R1","first-page":"1,968","volume-title":"Proceedings of the 3rd International Conference on Language Resources and Evaluation (LREC 2002)","author":"Afonso Susana","year":"2002"},{"key":"R2","first-page":"243","volume-title":"Proceedings of EACL Workshop on Linguistically Interpreted Corpora (LINC-03)","author":"Atalay Nart B.","year":"2003"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.3115\/1596276.1596307"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.3115\/1557690.1557729"},{"key":"R5","first-page":"195","volume-title":"Proceedings of FG-MoL 2005: The 10th Conference on Formal Grammar","author":"Bodirsky Manuel","year":"2005"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-010-0201-1_7"},{"key":"R7","first-page":"24","volume-title":"Proceedings of the 1st Workshop on Treebanks and Linguistic Theories (TLT)","author":"Brants Sabine","year":"2002"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.3115\/1596276.1596305"},{"key":"R9","first-page":"982","volume-title":"Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP)","author":"Buyko Ekaterina","year":"2010"},{"key":"R10","first-page":"957","volume-title":"Proceedings of the CoNLL Shared Task of EMNLP-CoNLL 2007","author":"Carreras Xavier","year":"2007"},{"key":"R11","first-page":"1,234","volume-title":"Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing (EMNLP 2011)","author":"Cohen Shay B.","year":"2011"},{"key":"R12","volume-title":"Introduction to Algorithms.","author":"Cormen Thomas H.","year":"1990"},{"key":"R13","first-page":"95","volume-title":"Proceedings of the 39th Annual ACM Southeast Conference","author":"Covington Michael A.","year":"2001"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.3115\/1218955.1219009"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.3115\/992628.992688"},{"key":"R16","first-page":"742","volume-title":"Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL HLT)","author":"Goldberg Yoav","year":"2010"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00060"},{"key":"R18","first-page":"1,492","volume-title":"Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL)","author":"G\u00f3mez-Rodr\u00edguez Carlos","year":"2010"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.3115\/1609067.1609099"},{"key":"R21","first-page":"110","volume-title":"Proceedings of the NEMLAR International Conference on Arabic Language Resources and Tools","author":"Haji\u010d Jan","year":"2004"},{"key":"R23","first-page":"608","volume-title":"Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics","author":"Havelka Jiri","year":"2007"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.3115\/1699648.1699668"},{"key":"R25","first-page":"1,077","volume-title":"Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Huang Liang","year":"2010"},{"key":"R26","volume-title":"English Word Grammar.","author":"Hudson Richard A.","year":"1990"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.3115\/1596276.1596315"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.3115\/980845.980953"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R30","first-page":"1","volume-title":"Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Koo Terry","year":"2010"},{"key":"R31","first-page":"1,288","volume-title":"Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing","author":"Koo Terry","year":"2010"},{"key":"R32","first-page":"217","volume-title":"Proceedings of the 2nd Workshop on Treebanks and Linguistic Theories (TLT)","author":"Kromann Matthias Trautner","year":"2003"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14568-1"},{"key":"R34","first-page":"673","volume-title":"Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Kuhlmann Marco","year":"2011"},{"key":"R35","first-page":"160","volume-title":"Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics","author":"Kuhlmann Marco","year":"2007"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.3115\/1273073.1273139"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.3115\/1609067.1609120"},{"key":"R38","first-page":"164","volume-title":"Proceedings of the 14th Conference on Formal Grammar","author":"Maier Wolfgang","year":"2009"},{"key":"R39","first-page":"313","volume":"19","author":"Marcus Mitchell P.","year":"1993","journal-title":"Computational Linguistics"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.3115\/1075812.1075835"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.3115\/1687878.1687928"},{"key":"R42","first-page":"34","volume-title":"Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP)","author":"Martins Andre","year":"2010"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.3115\/1219840.1219852"},{"key":"R44","first-page":"122","volume-title":"Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL)","author":"McDonald Ryan","year":"2007"},{"key":"R45","first-page":"81","volume-title":"Proceedings of the 11th Conference of the European Chapter of the Association for Computational Linguistics (EACL)","author":"McDonald Ryan","year":"2006"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.3115\/1621410.1621426"},{"key":"R47","volume-title":"Dependency Syntax: Theory and Practice.","author":"Mel'\u010duk Igor","year":"1988"},{"key":"R48","first-page":"952","volume-title":"Proceedings of the CoNLL Shared Task of EMNLP-CoNLL 2007","author":"Nakagawa Tetsuji","year":"2007"},{"key":"R49","first-page":"121","volume-title":"Proceedings of the NODALIDA Special Session on Treebanks","author":"Nilsson Jens","year":"2005"},{"key":"R50","first-page":"149","volume-title":"Proceedings of the 8th International Workshop on Parsing Technologies (IWPT)","author":"Nivre Joakim","year":"2003"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.3115\/1613148.1613156"},{"key":"R52","first-page":"73","volume-title":"Proceedings of the 11th Conference of the European Chapter of the Association for Computational Linguistics (EACL)","author":"Nivre Joakim","year":"2006"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1007\/1-4020-4889-0"},{"key":"R54","first-page":"396","volume-title":"Proceedings of Human Language Technologies: The Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL HLT)","author":"Nivre Joakim","year":"2007"},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.1162\/coli.07-056-R1-07-027"},{"key":"R56","doi-asserted-by":"publisher","DOI":"10.3115\/1687878.1687929"},{"key":"R57","first-page":"49","volume-title":"Proceedings of the 8th Conference on Computational Natural Language Learning (CoNLL)","author":"Nivre Joakim","year":"2004"},{"key":"R58","first-page":"2,216","volume-title":"Proceedings of the 5th International Conference on Language Resources and Evaluation (LREC)","author":"Nivre Joakim","year":"2006"},{"key":"R59","doi-asserted-by":"publisher","DOI":"10.3115\/1596276.1596318"},{"key":"R60","doi-asserted-by":"publisher","DOI":"10.3115\/1219840.1219853"},{"key":"R61","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-010-0201-1_15"},{"key":"R62","doi-asserted-by":"publisher","DOI":"10.3115\/1219840.1219874"},{"key":"R63","doi-asserted-by":"publisher","DOI":"10.3115\/1610075.1610095"},{"key":"R64","doi-asserted-by":"publisher","DOI":"10.3115\/1599081.1599176"},{"key":"R65","volume-title":"The Meaning of the Sentence in Its Pragmatic Aspects.","author":"Sgall Petr","year":"1986"},{"key":"R66","doi-asserted-by":"publisher","DOI":"10.3115\/1220175.1220287"},{"key":"R67","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(95)00035-I"},{"key":"R68","doi-asserted-by":"publisher","DOI":"10.3115\/1613715.1613737"},{"key":"R69","doi-asserted-by":"publisher","DOI":"10.3115\/1641408.1641410"},{"key":"R70","volume-title":"\u00c9l\u00e9ments de syntaxe structurale.","author":"Tesni\u00e8re Lucien","year":"1959"},{"key":"R71","doi-asserted-by":"publisher","DOI":"10.3115\/1621410.1621428"},{"key":"R72","first-page":"1,257","volume-title":"Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing","author":"Tratz Stephen","year":"2011"},{"key":"R73","doi-asserted-by":"publisher","DOI":"10.1163\/9789004334038_003"},{"key":"R74","doi-asserted-by":"publisher","DOI":"10.3115\/1620754.1620790"},{"key":"R75","first-page":"195","volume-title":"Proceedings of the 8th International Workshop on Parsing Technologies (IWPT)","author":"Yamada Hiroyasu","year":"2003"},{"key":"R76","first-page":"189","volume-title":"Proceedings of the 2nd Workshop on Treebanks and Linguistic Theories (TLT)","author":"Yli-Jyr\u00e4 Anssi","year":"2003"},{"key":"R77","doi-asserted-by":"publisher","DOI":"10.3115\/1613715.1613784"},{"key":"R78","first-page":"188","volume-title":"Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics (ACL)","author":"Zhang Yue","year":"2011"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/COLI_a_00150","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:27:26Z","timestamp":1615584446000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/39\/4\/799-845\/1459"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":76,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1162\/COLI_a_00150"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00150","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12]]}}}