{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T20:48:57Z","timestamp":1648673337873},"reference-count":28,"publisher":"Cambridge University Press (CUP)","license":[{"start":{"date-parts":[[2015,7,23]],"date-time":"2015-07-23T00:00:00Z","timestamp":1437609600000},"content-version":"unspecified","delay-in-days":203,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2015]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a divide-and-conquer algorithm for parsing context-free languages efficiently. Our algorithm is an instance of Valiant's (1975; General context-free recognition in less than cubic time. <jats:italic>J. Comput. Syst. Sci.<\/jats:italic><jats:bold>10<\/jats:bold>(2), 308\u2013314), who reduced the problem of parsing to matrix multiplications. We show that, while the conquer step of Valiant's is <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>3<\/jats:sup>), it improves to <jats:italic>O<\/jats:italic>(log<jats:sup>2<\/jats:sup><jats:italic>n<\/jats:italic>) under certain conditions satisfied by many useful inputs that occur in practice, and if one uses a sparse representation of matrices. The improvement happens because the multiplications involve an overwhelming majority of empty matrices. This result is relevant to modern computing: divide-and-conquer algorithms with a polylogarithmic conquer step can be parallelized relatively easily.<\/jats:p>","DOI":"10.1017\/s0956796815000131","type":"journal-article","created":{"date-parts":[[2015,7,23]],"date-time":"2015-07-23T00:50:05Z","timestamp":1437612605000},"source":"Crossref","is-referenced-by-count":0,"title":["Efficient parallel and incremental parsing of practical context-free languages"],"prefix":"10.1017","volume":"25","author":[{"given":"JEAN-PHILIPPE","family":"BERNARDY","sequence":"first","affiliation":[]},{"given":"KOEN","family":"CLAESSEN","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2015,7,23]]},"reference":[{"key":"S0956796815000131_ref12","first-page":"175","volume-title":"BNFC Quick reference","author":"Forsberg"},{"key":"S0956796815000131_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.09.011"},{"key":"S0956796815000131_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/2048066.2048101"},{"key":"S0956796815000131_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-1885-0"},{"key":"S0956796815000131_ref21","unstructured":"O'Sullivan B. (2013) The Criterion benchmarking library."},{"key":"S0956796815000131_ref19","doi-asserted-by":"publisher","DOI":"10.1145\/1273442.1250752"},{"key":"S0956796815000131_ref22","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90070-3"},{"key":"S0956796815000131_ref3","doi-asserted-by":"publisher","DOI":"10.1145\/1596638.1596645"},{"key":"S0956796815000131_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796804005192"},{"key":"S0956796815000131_ref13","unstructured":"Free Software Foundation. (1991) Gnu general public license."},{"key":"S0956796815000131_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90202-7"},{"key":"S0956796815000131_ref2","doi-asserted-by":"publisher","DOI":"10.1145\/1411286.1411294"},{"key":"S0956796815000131_ref4","unstructured":"Bernardy J.-P. and Claessen K. (2013) Efficient divide-and-conquer parsing of practical context-free languages. In Proceedings of the 18th ACM SIGPLAN International Conference on Funct. Programming, pp. 111\u2013122."},{"key":"S0956796815000131_ref5","volume-title":"An Introduction to the Theory of Lists","author":"Bird","year":"1986"},{"key":"S0956796815000131_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(59)90362-6"},{"key":"S0956796815000131_ref10","volume-title":"Programming Languages and their Compilers: Preliminary Notes","author":"Cocke","year":"1969"},{"key":"S0956796815000131_ref11","volume-title":"Introduction to Algorithms","author":"Cormen","year":"2001"},{"key":"S0956796815000131_ref17","unstructured":"Kasami T. (1965) An Efficient Recognition and Syntax Analysis Algorithm for Context-Free Languages. Technical Report, DTIC Document."},{"key":"S0956796815000131_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796805005769"},{"key":"S0956796815000131_ref16","doi-asserted-by":"crossref","unstructured":"Hughes R. J. M. & Swierstra S. D. (2003) Polish parsers, step by step. In Proceedings of the Eighth ACM SIGPLAN International Conference on Funct. Programming. ACM, pp. 239\u2013248.","DOI":"10.1145\/944705.944727"},{"key":"S0956796815000131_ref23","first-page":"61","volume-title":"Parsing of Context-Free Languages","author":"Sikkel","year":"1997"},{"key":"S0956796815000131_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)80007-X"},{"key":"S0956796815000131_ref27","doi-asserted-by":"publisher","DOI":"10.1145\/293677.293678"},{"key":"S0956796815000131_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90199-C"},{"key":"S0956796815000131_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"S0956796815000131_ref14","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800001908"},{"key":"S0956796815000131_ref18","first-page":"2008","article-title":"To CNF or not to CNF? An efficient yet presentable version of the CYK algorithm","volume":"8","author":"Lange","year":"2009","journal-title":"Inform. Didactica"},{"key":"S0956796815000131_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80046-8"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796815000131","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T22:28:34Z","timestamp":1559860114000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796815000131\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"references-count":28,"alternative-id":["S0956796815000131"],"URL":"https:\/\/doi.org\/10.1017\/s0956796815000131","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"article-number":"e10"}}