{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:27:16Z","timestamp":1759638436629},"reference-count":86,"publisher":"MIT Press - Journals","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2017,9]]},"abstract":"<jats:p> We explore the concept of hybrid grammars, which formalize and generalize a range of existing frameworks for dealing with discontinuous syntactic structures. Covered are both discontinuous phrase structures and non-projective dependency structures. Technically, hybrid grammars are related to synchronous grammars, where one grammar component generates linear structures and another generates hierarchical structures. By coupling lexical elements of both components together, discontinuous structures result. Several types of hybrid grammars are characterized. We also discuss grammar induction from treebanks. The main advantage over existing frameworks is the ability of hybrid grammars to separate discontinuity of the desired structures from time complexity of parsing. This permits exploration of a large variety of parsing algorithms for discontinuous structures, with different properties. This is confirmed by the reported experimental results, which show a wide variety of running time, accuracy, and frequency of parse failures. <\/jats:p>","DOI":"10.1162\/coli_a_00291","type":"journal-article","created":{"date-parts":[[2017,6,9]],"date-time":"2017-06-09T17:06:51Z","timestamp":1497028011000},"page":"465-520","source":"Crossref","is-referenced-by-count":8,"title":["Hybrid Grammars for Parsing of Discontinuous Phrase Structures and Non-Projective Dependency Structures"],"prefix":"10.1162","volume":"43","author":[{"given":"Kilian","family":"Gebhardt","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Dresden"}]},{"given":"Mark-Jan","family":"Nederhof","sequence":"additional","affiliation":[{"name":"University of St. Andrews"}]},{"given":"Heiko","family":"Vogler","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Dresden"}]}],"member":"281","reference":[{"key":"bib1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-76336-9_3"},{"key":"bib2","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/E14-1039"},{"key":"bib3","doi-asserted-by":"publisher","DOI":"10.3115\/977180.977185"},{"key":"bib4","unstructured":"Blunsom, P. and T. Cohn. 2010. Unsupervised induction of tree substitution grammars for dependency parsing. In Conference on Empirical Methods in Natural Language Processing, Proceedings of the Conference, pages 1204\u20131213, Massachusetts."},{"key":"bib5","doi-asserted-by":"publisher","DOI":"10.1145\/359997.359999"},{"key":"bib6","unstructured":"Bodirsky, M., M. Kuhlmann, and M. M\u00f6hl. 2005. Well-nested drawings as models of syntactic structure. In Proceedings of the 10th Conference on Formal Grammar and 9th Meeting on Mathematics of Language, pages 195\u2013203, Edinburgh."},{"key":"bib8","doi-asserted-by":"crossref","unstructured":"Boyd, A.2007. Discontinuity revisited: An improved conversion to context-free representations. In Proceedings of the Linguistic Annotation Workshop, at ACL 2007, pages 41\u201344, Prague.","DOI":"10.3115\/1642059.1642065"},{"key":"bib9","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(69)90065-5"},{"key":"bib10","doi-asserted-by":"publisher","DOI":"10.1007\/s11168-004-7431-3"},{"key":"bib11","unstructured":"Bresnan, J., R. M. Kaplan, S. Peters, and A. Zaenen. 1982. Cross-serial dependencies in Dutch. Linguistic Inquiry, 13(4):613\u2013635."},{"key":"bib12","doi-asserted-by":"publisher","DOI":"10.3115\/1596276.1596305"},{"key":"bib13","doi-asserted-by":"crossref","unstructured":"Campbell, R.2004. Using linguistic principles to recover empty categories. In 42nd Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, pages 645\u2013652, Barcelona.","DOI":"10.3115\/1218955.1219037"},{"key":"bib14","unstructured":"Charniak, E.1996. Tree-bank grammars. In AAAI 96 Proceedings, pages 1031\u20131036, Portland, OR."},{"key":"bib15","unstructured":"Charniak, E.2000. A maximumentropy-inspired parser. In 6th Applied Natural Language Processing Conference and 1st Meeting of the North American Chapter of the Association for Computational Linguistics, pages 132\u2013139 (Section 2), Seattle, WA."},{"key":"bib16","unstructured":"Charniak, E., K. Knight, and K. Yamada. 2003. Syntax-based language models for statistical machine translation. In Proceedings of the Ninth Machine Translation Summit, pages 40\u201346, New Orleans, LA."},{"key":"bib17","doi-asserted-by":"crossref","unstructured":"Chen, D. and C. D. Manning. 2014. A fast and accurate dependency parser using neural networks. In Conference on Empirical Methods in Natural Language Processing, Proceedings of the Conference, pages 740\u2013750, Doha.","DOI":"10.3115\/v1\/D14-1082"},{"key":"bib19","doi-asserted-by":"publisher","DOI":"10.3115\/976909.979620"},{"key":"bib20","unstructured":"Collins, M. 2000. Discriminative reranking for natural language parsing. In Proceedings of the Seventeenth International Conference on Machine Learning, pages 175\u2013182, Stanford, CA."},{"key":"bib21","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90003-2"},{"key":"bib22","unstructured":"van Cranenburgh, A.2012. Efficient parsing with linear context-free rewriting systems. In Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 460\u2013470, Avignon."},{"key":"bib23","unstructured":"Daniels, M. and W. D. Meurers. 2002. Improving the efficiency of parsing with discontinuous constituents. In Proceedings of NLULP\u201902: The 7th International Workshop on Natural Language Understanding and Logic Programming, pages 49\u201368, Copenhagen."},{"key":"bib24","doi-asserted-by":"crossref","unstructured":"Daniels, M. W. and W. D. Meurers. 2004. A grammar formalism and parser for linearization-based HPSG. In the 20th International Conference on Computational Linguistics, volume 1, pages 169\u2013175, Geneva.","DOI":"10.3115\/1220355.1220380"},{"key":"bib26","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(85)90015-9"},{"key":"bib27","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(77)90309-6"},{"key":"bib28","doi-asserted-by":"crossref","unstructured":"Eisner, J. 1996. Three new probabilistic models for dependency parsing: An exploration. In the 16th International Conference on Computational Linguistics, volume 1, pages 340\u2013345, Copenhagen.","DOI":"10.3115\/992628.992688"},{"key":"bib29","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289307"},{"key":"bib30","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(77)80034-2"},{"key":"bib31","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90051-X"},{"key":"bib32","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1573"},{"key":"bib33","unstructured":"Evang, K. and L. Kallmeyer. 2011. PLCFRS parsing of English discontinuous constituents. In Proceedings of the 12th International Conference on Parsing Technologies, pages 104\u2013116, Dublin."},{"key":"bib34","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1968.12"},{"key":"bib35","unstructured":"Fouvry, F. and D. Meurers. 2000. Towards a platform for linearization grammars. In Proceedings of the Workshop on Linguistic Theory and Grammar Implementation, at ESSLLI-2000, pages 153\u2013168, Birmingham."},{"key":"bib36","unstructured":"F\u00fcl\u00f6p, Z. and H. Vogler. 1999. A characterization of attributed tree transformations by a subclass of macro tree transducers. Theoretical Computer Science, 32:649\u2013676."},{"key":"bib37","doi-asserted-by":"crossref","unstructured":"Gabbard, R., S. Kulick, and M. Marcus. 2006. Fully parsing the Penn Treebank. In Proceedings of the Human Language Technology Conference of the NAACL, Main Conference, pages 184\u2013191, New York.","DOI":"10.3115\/1220835.1220859"},{"key":"bib38","unstructured":"Gebhardt, K. and J. Osterholzer. 2015. A direct link between tree-adjoining and context-free tree grammars. In Proceedings of the 12th International Conference on Finite-State Methods and Natural Language Processing (FSMNLP 2015), D\u00fcsseldorf."},{"key":"bib40","doi-asserted-by":"publisher","DOI":"10.1007\/BF02737108"},{"key":"bib41","unstructured":"G\u00f3mez-Rodr\u00edguez, C., M. Kuhlmann, and G. Satta. 2010. Efficient parsing of well-nested linear context-free rewriting systems. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Proceedings of the Main Conference, pages 276\u2013284, Los Angeles, CA."},{"key":"bib42","doi-asserted-by":"publisher","DOI":"10.3115\/1620754.1620833"},{"key":"bib43","doi-asserted-by":"crossref","unstructured":"G\u00f3mez-Rodr\u00edguez, C. and G. Satta. 2009. An optimal-time binarization algorithm for linear context-free rewriting systems with fan-out two. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pages 985\u2013993, Suntec.","DOI":"10.3115\/1690219.1690284"},{"key":"bib44","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/W16-2409"},{"key":"bib45","doi-asserted-by":"crossref","unstructured":"Henderson, J. 2004. Discriminative training of a neural network statistical parser. In 42nd Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, pages 95\u2013102, Barcelona.","DOI":"10.3115\/1218955.1218968"},{"key":"bib46","doi-asserted-by":"publisher","DOI":"10.1162\/coli.2007.33.3.355"},{"key":"bib47","doi-asserted-by":"crossref","unstructured":"Johnson, M. 2002. A simple pattern-matching algorithm for recovering empty nodes and their antecedents. In 40th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, pages 136\u2013143, Philadelphia, PA.","DOI":"10.3115\/1073083.1073107"},{"key":"bib48","doi-asserted-by":"crossref","unstructured":"Kahane, S., A. Nasr, and O. Rambow. 1998. Pseudo-projectivity, a polynomially parsable non-projective dependency grammar. In 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, volume 1, pages 646\u2013652, Montreal.","DOI":"10.3115\/980845.980953"},{"key":"bib49","unstructured":"Kallmeyer, K. and M. Kuhlmann. 2012. A formal model for plausible dependencies in lexicalized tree adjoining grammar. In Eleventh International Workshop on Tree Adjoining Grammar and Related Formalisms, pages 108\u2013116, Paris."},{"key":"bib50","unstructured":"Kallmeyer, L. and W. Maier. 2010. Data-driven parsing with probabilistic linear context-free rewriting systems. In the 23rd International Conference on Computational Linguistics, pages 537\u2013545, Beijing."},{"key":"bib51","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00136"},{"key":"bib54","doi-asserted-by":"crossref","unstructured":"Kanazawa, M. and S. Salvati. 2010. The copying power of well-nested multiple context-free grammars. In Language and Automata Theory and Applications, volume 6031 of Lecture Notes in Computer Science, pages 344\u2013355, Trier.","DOI":"10.1007\/978-3-642-13089-2_29"},{"key":"bib55","doi-asserted-by":"publisher","DOI":"10.3115\/981658.981682"},{"key":"bib56","doi-asserted-by":"publisher","DOI":"10.1007\/s10849-011-9134-0"},{"key":"bib57","doi-asserted-by":"crossref","unstructured":"Klein, D. and C. Manning. 2004. Corpus-based induction of syntactic structure: Models of dependency and constituency. In 42nd Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, pages 478\u2013485, Barcelona.","DOI":"10.3115\/1218955.1219016"},{"key":"bib58","doi-asserted-by":"publisher","DOI":"10.3115\/1073445.1073461"},{"key":"bib61","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00125"},{"key":"bib62","doi-asserted-by":"publisher","DOI":"10.3115\/1609067.1609120"},{"key":"bib63","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70590-1_15"},{"key":"bib64","doi-asserted-by":"crossref","unstructured":"Lu, W., H. T. Ng, W. S. Lee, and L. S. Zettlemoyer. 2008. A generative model for parsing natural language to meaning representations. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 783\u2013792, Honolulu, HI.","DOI":"10.3115\/1613715.1613815"},{"key":"bib65","unstructured":"Maier, W. and L. Kallmeyer. 2010. Discontinuity and non-projectivity: Using mildly context-sensitive formalisms for data-driven parsing. In Tenth International Workshop on Tree Adjoining Grammar and Related Formalisms, pages 119\u2013126, New Haven, CT."},{"key":"bib66","unstructured":"Maier, W. and A. S\u00f8gaard. 2008. Treebanks and mild context-sensitivity. In Proceedings of the 13th Conference on Formal Grammar, pages 61\u201376, Hamburg."},{"key":"bib67","doi-asserted-by":"crossref","unstructured":"Maier, Wolfgang and Timm Lichte. 2009. Characterizing discontinuity in constituent treebanks. In Proceedings of the 14th Conference on Formal Grammar, volume 5591 of Lecture Notes in Artificial Intelligence, pages 167\u2013182, Bordeaux.","DOI":"10.1007\/978-3-642-20169-1_11"},{"key":"bib68","unstructured":"Maletti, A. and J. Engelfriet. 2012. Strong lexicalization of tree adjoining grammars. In 50th Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, pages 506\u2013515, Jeju Island."},{"key":"bib69","unstructured":"Marcus, M. P., B. Santorini, and M. A. Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313\u2013330."},{"key":"bib70","unstructured":"McCawley, J. D. 1982. Parentheticals and discontinuous constituent structure. Linguistic Inquiry, 13(1):91\u2013106."},{"key":"bib71","unstructured":"McDonald, R. and F. Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proceedings of the 11th Conference of the European Chapter of the Association for Computational Linguistics, pages 81\u201388, Trento."},{"key":"bib72","doi-asserted-by":"crossref","unstructured":"McDonald, R., F. Pereira, K. Ribarov, and J. Haji\u010d. 2005. Non-projective dependency parsing using spanning tree algorithms. In Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pages 523\u2013530, Vancouver.","DOI":"10.3115\/1220575.1220641"},{"key":"bib74","unstructured":"M\u00f6nnich, U. 2010. Well-nested tree languages and attributed tree transducers. In Tenth International Workshop on Tree Adjoining Grammar and Related Formalisms, pages 35\u201344, New Haven, CT."},{"key":"bib75","doi-asserted-by":"publisher","DOI":"10.1023\/B:ROLC.0000016785.49729.d7"},{"key":"bib76","unstructured":"Nederhof, M.J. and H. Vogler. 2014. Hybrid grammars for discontinuous parsing. In the 25th International Conference on Computational Linguistics: Technical Papers, pages 1370\u20131381, Dublin."},{"key":"bib78","doi-asserted-by":"crossref","unstructured":"Nivre, J. and J. Nilsson. 2005. Pseudo-projective dependency parsing. In 43rd Annual Meeting of the Association for Computational Linguistics, Proceedings of the Conference, pages 99\u2013106, Ann Arbor, MI.","DOI":"10.3115\/1219840.1219853"},{"key":"bib79","doi-asserted-by":"crossref","unstructured":"Nivre, Joakim. 2009. Non-projective dependency parsing in expected linear time. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pages 351\u2013359, Suntec.","DOI":"10.3115\/1687878.1687929"},{"key":"bib80","unstructured":"Nivre, Joakim, Johan Hall, and Jens Nilsson. 2006. Maltparser: A data-driven parser-generator for dependency parsing. In LREC 2006: Fifth International Conference on Language Resources and Evaluation, Proceedings, pages 2216\u20132219, Genoa."},{"key":"bib81","doi-asserted-by":"publisher","DOI":"10.3115\/1697236.1697250"},{"key":"bib82","doi-asserted-by":"publisher","DOI":"10.1145\/210376.197409"},{"key":"bib83","doi-asserted-by":"crossref","unstructured":"Petrov, S., L. Barrett, R. Thibaux, and D. Klein. 2006. Learning accurate, compact, and interpretable tree annotation. In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, pages 433\u2013440, Sydney.","DOI":"10.3115\/1220175.1220230"},{"key":"bib85","unstructured":"Rambow, O. 2010. The simple truth about dependency and phrase structure representations: An opinion piece. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Proceedings of the Main Conference, pages 337\u2013340, Los Angeles, CA."},{"key":"bib88","doi-asserted-by":"publisher","DOI":"10.3115\/976815.976829"},{"key":"bib90","doi-asserted-by":"publisher","DOI":"10.1007\/BF01695769"},{"key":"bib91","doi-asserted-by":"publisher","DOI":"10.1162\/tacl_a_00226"},{"key":"bib92","doi-asserted-by":"crossref","unstructured":"Satta, G. and E. Peserico. 2005. Some computational complexity results for synchronous context-free grammars. In Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pages 803\u2013810, Vancouver.","DOI":"10.3115\/1220575.1220676"},{"key":"bib94","doi-asserted-by":"publisher","DOI":"10.1093\/ietisy\/e91-d.2.209"},{"key":"bib95","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90374-B"},{"key":"bib96","doi-asserted-by":"publisher","DOI":"10.1007\/BF00630917"},{"key":"bib97","doi-asserted-by":"crossref","unstructured":"Shieber, S. M. and Y. Schabes. 1990. Synchronous tree-adjoining grammars. In Papers Presented to the 13th International Conference on Computational Linguistics, volume 3, pages 253\u2013258, Helsinki.","DOI":"10.3115\/991146.991191"},{"key":"bib98","unstructured":"Sima\u2019an, K., R. Bod, S. Krauwer, and R. Scha. 1994. Efficient disambiguation by means of stochastic tree substitution grammars. In Proceedings of International Conference on New Methods in Language Processing, pages 50\u201358, Manchester."},{"key":"bib99","doi-asserted-by":"publisher","DOI":"10.3115\/974557.974571"},{"key":"bib101","doi-asserted-by":"publisher","DOI":"10.3115\/981210.981221"},{"key":"bib102","doi-asserted-by":"publisher","DOI":"10.3115\/981175.981190"}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/COLI_a_00291","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:28:06Z","timestamp":1615584486000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/43\/3\/465-520\/1579"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9]]},"references-count":86,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["10.1162\/COLI_a_00291"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00291","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9]]}}}