{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T20:11:48Z","timestamp":1784232708848,"version":"3.55.0"},"reference-count":70,"publisher":"MIT Press - Journals","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2013,3]]},"abstract":"<jats:p> This paper presents the first efficient implementation of a weighted deductive CYK parser for Probabilistic Linear Context-Free Rewriting Systems (PLCFRSs). LCFRS, an extension of CFG, can describe discontinuities in a straightforward way and is therefore a natural candidate to be used for data-driven parsing. To speed up parsing, we use different context-summary estimates of parse items, some of them allowing for A* parsing. We evaluate our parser with grammars extracted from the German NeGra treebank. Our experiments show that data-driven LCFRS parsing is feasible and yields output of competitive quality. <\/jats:p>","DOI":"10.1162\/coli_a_00136","type":"journal-article","created":{"date-parts":[[2012,11,13]],"date-time":"2012-11-13T14:42:31Z","timestamp":1352817751000},"page":"87-119","source":"Crossref","is-referenced-by-count":9,"title":["Data-Driven Parsing using Probabilistic Linear Context-Free Rewriting Systems"],"prefix":"10.1162","volume":"39","author":[{"given":"Laura","family":"Kallmeyer","sequence":"first","affiliation":[{"name":"Heinrich-Heine-Universit\u00e4t D\u00fcsseldorf"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wolfgang","family":"Maier","sequence":"additional","affiliation":[{"name":"Heinrich-Heine-Universit\u00e4t D\u00fcsseldorf"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"281","reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.3115\/1073012.1073019"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.3115\/977180.977185"},{"key":"R3","first-page":"17","volume-title":"Proceedings of the Fourth International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+4)","author":"Boullier Pierre","year":"1998"},{"key":"R5","first-page":"53","volume-title":"Proceedings of the Sixth International Workshop on Parsing Technologies (IWPT2000)","author":"Boullier Pierre","year":"2000"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.3115\/1642059.1642065"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.3115\/1621401.1621405"},{"key":"R8","first-page":"24","volume-title":"Proceedings of the 1st Workshop on Treebanks and Linguistic Theories","author":"Brants Sabine","year":"2002"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1515\/9783110873467"},{"key":"R10","first-page":"212","volume-title":"Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies","author":"Cai Shu","year":"2011"},{"key":"R11","first-page":"76","volume-title":"Proceedings of the First Workshop on Statistical Parsing of Morphologically-Rich Languages at NAACL HLT 2010","author":"Candito Marie","year":"2010"},{"issue":"2","key":"R12","first-page":"275","volume":"24","author":"Caraballo Sharon A.","year":"1998","journal-title":"Computational Linguistics"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.3115\/1220835.1220857"},{"key":"R14","first-page":"119","volume-title":"Proceedings of the Tenth International Workshop on Tree Adjoining Grammar and Related Formalisms (TAG+10)","author":"Chen-Main Joan","year":"2010"},{"key":"R15","first-page":"299","volume-title":"Data-Oriented Parsing, CSLI Studies in Computational Linguistics.","author":"Chiang David","year":"2003"},{"key":"R16","unstructured":"Collins, Michael. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania."},{"key":"R17","volume-title":"Introduction to Algorithms.","author":"Cormen Thomas H.","year":"2003","edition":"2"},{"key":"R18","unstructured":"Dienes, P\u00e9ter. 2003. Statistical Parsing with Non-local Dependencies. Ph.D. thesis, Saarland University."},{"key":"R19","first-page":"104","volume-title":"Proceedings of the 12th International Conference on Parsing Technologies","author":"Evang Kilian","year":"2011"},{"key":"R20","first-page":"276","volume-title":"Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics","author":"G\u00f3mez-Rodr\u00edguez Carlos","year":"2010"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.3115\/1620754.1620833"},{"key":"R22","first-page":"125","volume-title":"Data-Oriented Parsing","author":"Goodman Joshua","year":"2003"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.3115\/1621401.1621408"},{"key":"R25","unstructured":"Hockenmaier, Julia. 2003. Data and models for Statistical Parsing with Combinatory Categorial Grammar. Ph.D. thesis, University of Edinburgh."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.3115\/976973.977008"},{"key":"R27","volume-title":"Akten des Siebten Internationalen Germanistenkongresses 1985","author":"H\u00f6hle Tilman","year":"1986"},{"key":"R28","first-page":"136","volume-title":"Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics","author":"Johnson Mark","year":"2002"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14846-0"},{"key":"R30","first-page":"537","volume-title":"Proceedings of the 23rd International Conference on Computational Linguistics (COLING 2010)","author":"Kallmeyer Laura","year":"2010"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.3115\/1654690.1654698"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.3115\/1073445.1073461"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.3115\/1075096.1075150"},{"key":"R34","first-page":"3","volume-title":"Advances in Neural Information Processing Systems 15 (NIPS)","author":"Klein Dan","year":"2003"},{"key":"R35","volume-title":"The Mathematics of Language. Number 63 in Studies in Generative Grammar.","author":"Kracht Marcus","year":"2003"},{"key":"R36","first-page":"293","volume-title":"Recent Advances in Natural Language Processing 2005 (RANLP 2005)","author":"K\u00fcbler Sandra","year":"2005"},{"key":"R37","volume-title":"Proceedings of the Workshop on Parsing German at ACL 2008.","author":"K\u00fcbler Sandra","year":"2008"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.3115\/1609067.1609120"},{"key":"R39","unstructured":"Levy, Roger. 2005. Probabilistic Models of Word Order and Syntactic Discontinuity. Ph.D. thesis, Stanford University."},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.3115\/1218955.1218997"},{"key":"R41","first-page":"1420","volume-title":"Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI 95)","author":"Lin Dekang","year":"1995"},{"key":"R42","first-page":"58","volume-title":"Proceedings of the First Workshop on Statistical Parsing of Morphologically-Rich Languages at NAACL HLT 2010","author":"Maier Wolfgang","year":"2010"},{"key":"R43","first-page":"126","volume-title":"Proceedings of the Eleventh International Conference on Tree Adjoining Grammars and Related Formalisms (TAG+11)","author":"Maier Wolfgang","year":"2012"},{"key":"R44","volume-title":"Proceedings of the Tenth International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+10)","author":"Maier Wolfgang","year":"2010"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20169-1_11"},{"key":"R46","first-page":"61","volume-title":"Proceedings of the 13th Conference on Formal Grammar (FG-2008)","author":"Maier Wolfgang","year":"2008"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.3115\/1075812.1075835"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.3115\/1220575.1220641"},{"key":"R49","unstructured":"Michaelis, Jens. 2001. On Formal Properties of Minimalist Grammars. Ph.D. thesis, Universit\u00e4t Potsdam."},{"key":"R50","first-page":"265","volume-title":"Resolving Conflicts in Grammars: Optimality Theory in Syntax, Morphology, and Phonology.","author":"M\u00fcller Gereon","year":"2002"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1023\/B:ROLC.0000016785.49729.d7"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1162\/089120103321337467"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1017\/S1351324906004505"},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.3115\/981311.981338"},{"key":"R56","first-page":"404","volume-title":"Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference","author":"Petrov Slav","year":"2007"},{"key":"R57","doi-asserted-by":"publisher","DOI":"10.3115\/1621401.1621406"},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1007\/1-4020-2295-6_5"},{"key":"R59","doi-asserted-by":"publisher","DOI":"10.3115\/1621401.1621407"},{"key":"R60","first-page":"337","volume-title":"Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics","author":"Rambow Owen","year":"2010"},{"key":"R61","first-page":"372","volume-title":"Proceedings of the 16th Nordic Conference of Computational Linguistics","author":"Rehbein Ines","year":"2007"},{"key":"R62","unstructured":"Schmid, Helmut. 2000. LoPar: Design and implementation. Arbeitspapiere des Sonderforschungsbereiches 340 149, IMS,University of Stuttgart, Stuttgart, Germany."},{"key":"R63","volume-title":"Proceedings of the First Workshop on Statistical Parsing of Morphologically-Rich Languages at NAACL HLT 2010.","author":"Seddah Djame","year":"2010"},{"key":"R64","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90374-B"},{"key":"R65","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(95)00035-I"},{"key":"R66","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60541-3"},{"key":"R67","doi-asserted-by":"publisher","DOI":"10.3115\/974557.974571"},{"key":"R69","first-page":"385","volume-title":"Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing","author":"Tsarfaty Reut","year":"2011"},{"key":"R70","doi-asserted-by":"crossref","unstructured":"Uszkoreit, Hans. 1986. Linear precedence in discontinuous constituents: Complex fronting in German. CSLI report CSLI-86-47, Center for the Study of Language and Information, Stanford University, Stanford, CA.","DOI":"10.1163\/9789004373204_016"},{"key":"R71","first-page":"460","volume-title":"Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics","author":"van Cranenburgh Andreas","year":"2012"},{"key":"R72","first-page":"34","volume-title":"Proceedings of the Second Workshop on Statistical Parsing of Morphologically Rich Languages (SPMRL 2011)","author":"van Cranenburgh Andreas","year":"2011"},{"key":"R73","first-page":"209","volume-title":"Proceedings of the Fourth Workshop on Treebanks and Linguistic Theories","author":"Versley Yannick","year":"2005"},{"key":"R74","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_00136","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:27:21Z","timestamp":1615584441000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/39\/1\/87-119\/1431"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3]]},"references-count":70,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["10.1162\/COLI_a_00136"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00136","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3]]}}}