{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T04:51:23Z","timestamp":1772772683177,"version":"3.50.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2006,5,1]],"date-time":"2006-05-01T00:00:00Z","timestamp":1146441600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2006,5]]},"abstract":"<jats:p>We present new results on the relation between purely symbolic context-free parsing strategies and their probabilistic counterparts. Such parsing strategies are seen as constructions of push-down devices from grammars. We show that preservation of probability distribution is possible under two conditions, viz. the correct-prefix property and the property of strong predictiveness. These results generalize existing results in the literature that were obtained by considering parsing strategies in isolation. From our general results, we also derive negative results on so-called generalized LR parsing.<\/jats:p>","DOI":"10.1145\/1147954.1147959","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"406-436","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Probabilistic parsing strategies"],"prefix":"10.1145","volume":"53","author":[{"given":"Mark-Jan","family":"Nederhof","sequence":"first","affiliation":[{"name":"University of Groningen, Groningen, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giorgio","family":"Satta","sequence":"additional","affiliation":[{"name":"University of Padua, Padua, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.3115\/1034678.1034759"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.3115\/981623.981641"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2772"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1973.223746"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/972450.972453"},{"key":"e_1_2_1_6_1","volume-title":"Statistical Language Learning","author":"Charniak E."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.3115\/1073012.1073029"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 12th National Conference on Artificial Intelligence.","volume":"1","author":"Charniak E."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.3115\/980845.980882"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/973215.973219"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/972732.972738"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.3115\/116580.116665"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.3115\/976909.979620"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/362007.362035"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90110-4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/973226.973230"},{"key":"e_1_2_1_17_1","volume-title":"Introduction to Formal Language Theory","author":"Harrison M."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0255(71)80007-5"},{"key":"e_1_2_1_19_1","first-page":"85","article-title":"Probabilistic GLR parsing. In Advances in Probabilistic and other Parsing Technologies, H. Bunt and A. Nijholt, Eds. Kluwer Academic Publishers, Dordrecht","volume":"5","author":"Inui K.","year":"2000","journal-title":"Chap."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/971764.971768"},{"key":"e_1_2_1_21_1","unstructured":"Jurafsky D. and Martin J. 2000. Speech and Language Processing. Prentice-Hall Englewood Cliffs NJ.   Jurafsky D. and Martin J. 2000. Speech and Language Processing. Prentice-Hall Englewood Cliffs NJ."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90426-2"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/646230.681872"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.3115\/981623.981640"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00199-6"},{"key":"e_1_2_1_26_1","first-page":"105","article-title":"Probabilistic parsing using left corner language models. In Advances in Probabilistic and other Parsing Technologies, H. Bunt and A. Nijholt, Eds. Kluwer Academic Publishers, Dordrecht","volume":"6","author":"Manning C.","year":"2000","journal-title":"Chap."},{"key":"e_1_2_1_27_1","unstructured":"Manning C. and Sch\u00fctze H. 1999. Foundations of Statistical Natural Language Processing. Massachusetts Institute of Technology Cambridge MA.   Manning C. and Sch\u00fctze H. 1999. Foundations of Statistical Natural Language Processing. Massachusetts Institute of Technology Cambridge MA."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.3115\/976744.976780"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.3115\/981732.981749"},{"key":"e_1_2_1_30_1","first-page":"35","article-title":"Increasing the applicability of LR parsing. In Recent Advances in Parsing Technology, H. Bunt and M. Tomita, Eds. Kluwer Academic Publishers, Dordrecht","volume":"3","author":"Nederhof M.-J.","year":"1996","journal-title":"Chap."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 8th International Workshop on Parsing Technologies. LORIA","author":"Nederhof M.-J."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.3115\/1218955.1219025"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.3115\/1218955.1219024"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 2nd International Workshop on Parsing Technologies","author":"Ng S.-K."},{"key":"e_1_2_1_35_1","series-title":"Lecture Notes in Computer Science","volume-title":"Normal Forms, and Parsing","author":"Nijholt A."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01007759"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288959"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.3115\/1034678.1034743"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1970.5"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.615455"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(72)90026-5"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1080\/01969727608927530"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(95)00035-I"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Sikkel K. 1997. Parsing Schemata. Springer-Verlag Berlin Germany.  Sikkel K. 1997. Parsing Schemata. Springer-Verlag Berlin Germany.","DOI":"10.1007\/978-3-642-60541-3"},{"key":"e_1_2_1_45_1","volume-title":"Linear Modeling: Background and Applications","author":"Sikkel K.","year":"1997"},{"key":"e_1_2_1_46_1","volume-title":"Parsing Theory","author":"Sippu S."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00268320"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5715\/jnlp.6.3_3"},{"key":"e_1_2_1_49_1","first-page":"167","article-title":"An efficient probabilistic context-free parsing algorithm that computes prefix probabilities","volume":"21","author":"Stolcke A.","year":"1995","journal-title":"Computat. Ling."},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the 4th International Workshop on Parsing Technologies (Prague and Karlovy Vary, Czech Republic). 234--249","author":"Tendeau F.","year":"1995"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.csl.2004.05.009"},{"key":"e_1_2_1_54_1","volume-title":"International Workshop","volume":"348","author":"Voisin F.","year":"1988"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the 2nd International Workshop on Parsing Technologies","author":"Wright J."},{"key":"e_1_2_1_56_1","first-page":"113","article-title":"GLR parsing with probability. In Generalized LR Parsing, M. Tomita, Ed. Kluwer Academic Publishers, Dordrecht","volume":"8","author":"Wright J.","year":"1991","journal-title":"Chap."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1147954.1147959","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1147954.1147959","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:43:53Z","timestamp":1750290233000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1147954.1147959"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,5]]}},"alternative-id":["10.1145\/1147954.1147959"],"URL":"https:\/\/doi.org\/10.1145\/1147954.1147959","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,5]]},"assertion":[{"value":"2006-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}