{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:09:28Z","timestamp":1760026168620,"version":"3.40.3"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319452784"},{"type":"electronic","value":"9783319452791"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-45279-1_7","type":"book-chapter","created":{"date-parts":[[2016,9,16]],"date-time":"2016-09-16T16:23:45Z","timestamp":1474043025000},"page":"95-109","source":"Crossref","is-referenced-by-count":5,"title":["Certified Derivative-Based Parsing of Regular Expressions"],"prefix":"10.1007","author":[{"given":"Raul","family":"Lopes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodrigo","family":"Ribeiro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlos","family":"Camar\u00e3o","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,17]]},"reference":[{"key":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/978-3-642-18098-9_7","volume-title":"Implementation and Application of Automata","author":"JB Almeida","year":"2011","unstructured":"Almeida, J.B., Moreira, N., Pereira, D., de Sousa, S.M.: Partial derivative automata formalized in Coq. In: Domaratzki, M., Salomaa, K. (eds.) CIAA 2010. LNCS, vol. 6482, pp. 59\u201368. Springer, Heidelberg (2011)"},{"issue":"2","key":"7_CR2","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0304-3975(95)00182-4","volume":"155","author":"V Antimirov","year":"1996","unstructured":"Antimirov, V.: Partial derivatives of regular expressions and finite automaton constructions. Theor. Comput. Sci. 155(2), 291\u2013319 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Bernardy, J.-P., Jansson, P.: Certified context-free parsing: a formalisation of valiant\u2019s algorithm in agda. CoRR, abs\/1601.07724 (2016)","DOI":"10.2168\/LMCS-12(2:6)2016"},{"key":"7_CR4","volume-title":"Interactive Theorem Proving and Program Development: Coq\u2019Art The Calculus of Inductive Constructions","author":"Y Bertot","year":"2010","unstructured":"Bertot, Y., Castran, P.: Interactive Theorem Proving and Program Development: Coq\u2019Art The Calculus of Inductive Constructions, 1st edn. Springer Publishing Company, Incorporated, Heidelberg (2010)","edition":"1"},{"key":"7_CR5","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1017\/S095679681300018X","volume":"23","author":"E Brady","year":"2013","unstructured":"Brady, E.: Idris, a general-purpose dependently typed programming language: design and implementation. J. Funct. Program. 23, 552\u2013593 (2013)","journal-title":"J. Funct. Program."},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Brady, E.: Programming and reasoning with algebraic effects and dependent types. In: Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming, ICFP 2013, pp. 133\u2013144. ACM, New York (2013)","DOI":"10.1145\/2500365.2500581"},{"issue":"4","key":"7_CR7","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1145\/321239.321249","volume":"11","author":"JA Brzozowski","year":"1964","unstructured":"Brzozowski, J.A.: Derivatives of regular expressions. J. ACM 11(4), 481\u2013494 (1964)","journal-title":"J. ACM"},{"issue":"9","key":"7_CR8","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1145\/1932681.1863585","volume":"45","author":"NA Danielsson","year":"2010","unstructured":"Danielsson, N.A.: Total parser combinators. SIGPLAN Not. 45(9), 285\u2013296 (2010)","journal-title":"SIGPLAN Not."},{"key":"7_CR9","unstructured":"Felleisen, M.D., Barski, C., Van Horn, D.: Realm of Racket: Learn to Program, One Game at a Time! Eight Students of Northeastern University, San Francisco (2013)"},{"key":"7_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/978-3-319-03545-1_7","volume-title":"Certified Programs and Proofs","author":"D Firsov","year":"2013","unstructured":"Firsov, D., Uustalu, T.: Certified parsing of regular languages. In: Gonthier, G., Norrish, M. (eds.) CPP 2013. LNCS, vol. 8307, pp. 98\u2013113. Springer, Heidelberg (2013)"},{"issue":"5\u20136","key":"7_CR11","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1016\/j.jlamp.2014.09.002","volume":"83","author":"D Firsov","year":"2014","unstructured":"Firsov, D., Uustalu, T.: Certified CYK parsing of context-free languages. J. Log. Algebr. Meth. Program. 83(5\u20136), 459\u2013468 (2014)","journal-title":"J. Log. Algebr. Meth. Program."},{"issue":"5\u20136","key":"7_CR12","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1016\/j.jlamp.2014.09.002","volume":"83","author":"D Firsov","year":"2014","unstructured":"Firsov, D., Uustalu, T.: Certified CYK parsing of context-free languages. J. Log. Algebr. Methods Program. 83(5\u20136), 459\u2013468 (2014). The 24th Nordic Workshop on Programming Theory (NWPT 2012)","journal-title":"J. Log. Algebr. Methods Program."},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Fischer, S., Huch, F., Wilke, T.: A play on regular expressions: Functional pearl. In: Proceedings of the 15th ACM SIGPLAN International Conference on Functional Programming, ICFP 2010, pp. 357\u2013368. ACM, New York (2010)","DOI":"10.1145\/1863543.1863594"},{"key":"7_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1007\/978-3-540-27836-8_53","volume-title":"Automata, Languages and Programming","author":"A Frisch","year":"2004","unstructured":"Frisch, A., Cardelli, L.: Greedy regular expression matching. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 618\u2013629. Springer, Heidelberg (2004)"},{"key":"7_CR15","unstructured":"GNU Grep home page. https:\/\/www.gnu.org\/software\/grep\/"},{"key":"7_CR16","volume-title":"Introduction to Automata Theory Languages and Computability","author":"JE Hopcroft","year":"2000","unstructured":"Hopcroft, J.E., Motwani, R., Rotwani, U., Ullman, J.D.: Introduction to Automata Theory Languages and Computability, 2nd edn. Addison-Wesley Longman Publishing Co., Inc., Boston (2000)","edition":"2"},{"key":"7_CR17","unstructured":"The Idris Tutorial. http:\/\/docs.idris-lang.org\/en\/latest\/tutorial\/"},{"key":"7_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/978-3-642-28869-2_20","volume-title":"Programming Languages and Systems","author":"J-H Jourdan","year":"2012","unstructured":"Jourdan, J.-H., Pottier, F., Leroy, X.: Validating LR(1) parsers. In: Seidl, H. (ed.) Programming Languages and Systems. LNCS, vol. 7211, pp. 397\u2013416. Springer, Heidelberg (2012)"},{"key":"7_CR19","unstructured":"Lesk, M.E., Schmidt, E.: Lex: a lexical analyzer generator. In: Unix, vol. ii. pp. 375\u2013387. W. B. Saunders Company, Philadelphia, PA, USA (1990)"},{"key":"7_CR20","unstructured":"The Lightyear Idris Parsing Combinator Library. https:\/\/github.com\/ziman\/lightyear\/"},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Lopes, R., Ribeiro, R., Camar\u00e3o, C.: Certified derivative based parsing of regular expressions \u2014 on-linerepository (2016). https:\/\/github.com\/raulfpl\/idrisregexp","DOI":"10.1007\/978-3-319-45279-1_7"},{"key":"7_CR22","unstructured":"Macedo, H.D., Oliveira, J.N.: Typing linear algebra: a biproduct-oriented approach. CoRR, abs\/1312.4818 (2013)"},{"key":"7_CR23","unstructured":"McBride, C.: Dependently Typed Functional Programs and their Proofs. Ph.D. thesis, Department of Informatics, University of Edinburgh (1999)"},{"issue":"1","key":"7_CR24","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1017\/S0956796803004829","volume":"14","author":"C McBride","year":"2004","unstructured":"McBride, C., McKinna, J.: The view from the left. J. Funct. Program. 14(1), 69\u2013111 (2004)","journal-title":"J. Funct. Program."},{"issue":"9","key":"7_CR25","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1145\/2034574.2034801","volume":"46","author":"M Might","year":"2011","unstructured":"Might, M., Darais, D., Spiewak, D.: Parsing with derivatives: a functional pearl. SIGPLAN Not. 46(9), 189\u2013195 (2011)","journal-title":"SIGPLAN Not."},{"key":"7_CR26","doi-asserted-by":"crossref","unstructured":"Norell, U.: Dependently typed programming in agda. In: Proceedings of the 4th International Workshop on Types in Language Design and Implementation, TLDI 2009, pp. 1\u20132. ACM, New York (2009)","DOI":"10.1007\/978-3-642-04652-0_5"},{"issue":"2","key":"7_CR27","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1017\/S0956796808007090","volume":"19","author":"S Owens","year":"2009","unstructured":"Owens, S., Reppy, J., Turon, A.: Regular-expression derivatives re-examined. J. Funct. Program. 19(2), 173\u2013190 (2009)","journal-title":"J. Funct. Program."},{"key":"7_CR28","volume-title":"Types and Programming Languages","author":"BC Pierce","year":"2002","unstructured":"Pierce, B.C.: Types and Programming Languages, 1st edn. The MIT Press, Cambridge (2002)","edition":"1"},{"key":"7_CR29","unstructured":"Google Regular Expression Library - re2. https:\/\/github.com\/google\/re2"},{"key":"7_CR30","series-title":"Studies in Logic and the Foundations of Mathematics","volume-title":"Lectures on the Curry-Howard Isomorphism","author":"MH S\u00f8rensen","year":"2006","unstructured":"S\u00f8rensen, M.H., Urzyczyn, P.: Lectures on the Curry-Howard Isomorphism. Studies in Logic and the Foundations of Mathematics, vol. 149. Elsevier Science Inc., New York (2006)"},{"key":"7_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/978-3-319-07151-0_13","volume-title":"Functional and Logic Programming","author":"M Sulzmann","year":"2014","unstructured":"Sulzmann, M., Lu, K.Z.M.: POSIX regular expression parsing with derivatives. In: Codish, M., Sumii, E. (eds.) FLOPS 2014. LNCS, vol. 8475, pp. 203\u2013220. Springer, Heidelberg (2014)"},{"key":"7_CR32","unstructured":"The Univalent Foundatiosn Program. Homotopy Type Theory: Univalent Foundations of Mathematics (2013). http:\/\/homotopytypetheory.org\/book\/"},{"issue":"2","key":"7_CR33","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","volume":"10","author":"LG Valiant","year":"1975","unstructured":"Valiant, L.G.: General context-free recognition in less than cubic time. J. Comput. Syst. Sci. 10(2), 308\u2013315 (1975)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Programming Languages"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-45279-1_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T13:06:56Z","timestamp":1568380016000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-45279-1_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319452784","9783319452791"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-45279-1_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}