{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T04:02:21Z","timestamp":1742961741565,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319986531"},{"type":"electronic","value":"9783319986548"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-98654-8_40","type":"book-chapter","created":{"date-parts":[[2018,8,4]],"date-time":"2018-08-04T19:43:57Z","timestamp":1533411837000},"page":"491-502","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The Computational Power of Parsing Expression Grammars"],"prefix":"10.1007","author":[{"given":"Bruno","family":"Loff","sequence":"first","affiliation":[]},{"given":"Nelma","family":"Moreira","sequence":"additional","affiliation":[]},{"given":"Rog\u00e9rio","family":"Reis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,5]]},"reference":[{"key":"40_CR1","volume-title":"The Theory of Parsing, Translation, and Compiling","author":"AV Aho","year":"1972","unstructured":"Aho, A.V., Ullman, J.D.: The Theory of Parsing, Translation, and Compiling, vol. 1. Prentice-Hall, Upper Saddle River (1972)"},{"key":"40_CR2","unstructured":"Amarilli, A., Jeanmougin, M.: A proof of the pumping lemma for context-free languages through pushdown automata \n                    arXiv:1207.2819\n                    \n                   (2012)"},{"key":"40_CR3","unstructured":"Bar-Hillel, Y., Perles, M., Shamir, E.: On formal properties of simple phrase structure grammars. In: Bar-Hillel, Y. (ed.) Language and Information: Selected Essays on their Theory and Application. Series in Logic, pp. 116\u2013150. Addison-Wesley (1964)"},{"key":"40_CR4","unstructured":"Birman, A.: The TMG recognition schema. Ph.D. thesis, Princeton (1970)"},{"key":"40_CR5","doi-asserted-by":"crossref","unstructured":"Birman, A., Ullman, J.D.: Parsing algorithms with backtrack. In: 11th Annual Symposium on Switching and Automata Theory, pp. 153\u2013174. IEEE (1970)","DOI":"10.1109\/SWAT.1970.18"},{"key":"40_CR6","unstructured":"Ford, B.: The packrat parsing and parsing expression grammars page. \n                    http:\/\/bford.info\/packrat\/"},{"key":"40_CR7","doi-asserted-by":"crossref","unstructured":"Ford, B.: Packrat parsing: a practical linear-time algorithm with backtracking. Massachusetts Institute of Technology (2002)","DOI":"10.1145\/581478.581483"},{"key":"40_CR8","doi-asserted-by":"crossref","unstructured":"Ford, B.: Packrat parsing: simple, powerful, lazy, linear time, functional pearl. In: Wand, M., Jones, S.L.P. (eds.) (ICFP 2002), pp. 36\u201347. ACM (2002)","DOI":"10.1145\/581478.581483"},{"key":"40_CR9","doi-asserted-by":"crossref","unstructured":"Ford, B.: Parsing expression grammars: a recognition-based syntactic foundation. In: ACM SIGPLAN Notices, vol. 39, pp. 111\u2013122. ACM (2004)","DOI":"10.1145\/964001.964011"},{"key":"40_CR10","unstructured":"Garnock-Jones, T., Eslamimehr, M., Warth, A.: Recognising and generating terms using derivatives of parsing expression grammars. CoRR abs\/1801.10490 (2018)"},{"issue":"4","key":"40_CR11","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"SA Greibach","year":"1973","unstructured":"Greibach, S.A.: The hardest context-free language. SIAM J. Comput. 2(4), 304\u2013310 (1973)","journal-title":"SIAM J. Comput."},{"key":"40_CR12","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J Hartmanis","year":"1965","unstructured":"Hartmanis, J., Stearns, R.E.: On the computational complexity of algorithms. Trans. Am. Math. Soc. 117, 285\u2013306 (1965)","journal-title":"Trans. Am. Math. Soc."},{"key":"40_CR13","doi-asserted-by":"publisher","first-page":"61","DOI":"10.2977\/prims\/1195192738","volume":"9","author":"T Hayashi","year":"1973","unstructured":"Hayashi, T.: On derivation trees of indexed grammars: an extension of the uvwxy-theorem. Publ. Res. Inst. Math. Sci. Kyoto Univ. 9, 61\u201392 (1973)","journal-title":"Publ. Res. Inst. Math. Sci. Kyoto Univ."},{"issue":"1","key":"40_CR14","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1145\/568438.568455","volume":"32","author":"JE Hopcroft","year":"2001","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to automata theory, languages, and computation. ACM SIGACT News 32(1), 60\u201365 (2001)","journal-title":"ACM SIGACT News"},{"issue":"2","key":"40_CR15","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S009753979324485X","volume":"24","author":"M Li","year":"1995","unstructured":"Li, M., Vit\u00e1nyi, P.: A new approach to formal language theory by Kolmogorov complexity. SIAM J. Comput. 24(2), 398\u2013410 (1995)","journal-title":"SIAM J. Comput."},{"key":"40_CR16","volume-title":"Introduction to the Theory of Computation","author":"M Sipser","year":"2012","unstructured":"Sipser, M.: Introduction to the Theory of Computation, 3rd edn. Cengage Learning, Boston (2012)","edition":"3"},{"issue":"1","key":"40_CR17","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0020-0190(89)90108-7","volume":"31","author":"S Yu","year":"1989","unstructured":"Yu, S.: A pumping lemma for deterministic context-free languages. Inf. Process. Lett. 31(1), 47\u201351 (1989)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-98654-8_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,9,2]],"date-time":"2018-09-02T19:20:06Z","timestamp":1535916006000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-98654-8_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319986531","9783319986548"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-98654-8_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}