{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:30:53Z","timestamp":1767929453419,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,9,21]],"date-time":"2017-09-21T00:00:00Z","timestamp":1505952000000},"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":[],"published-print":{"date-parts":[[2017,9,21]]},"DOI":"10.1145\/3125374.3125381","type":"proceedings-article","created":{"date-parts":[[2017,9,20]],"date-time":"2017-09-20T12:36:22Z","timestamp":1505910982000},"page":"1-8","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Certified Bit-Coded Regular Expression Parsing"],"prefix":"10.1145","author":[{"given":"Rodrigo","family":"Ribeiro","sequence":"first","affiliation":[{"name":"Universidade Federal de Ouro Preto, Ouro Preto, Minas Gerais - Brazil"}]},{"given":"Andr\u00e9 Du","family":"Bois","sequence":"additional","affiliation":[{"name":"Universidade Federal de Pelotas, Pelotas, Rio Grande do Sul - Brazil"}]}],"member":"320","published-online":{"date-parts":[[2017,9,21]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1964285.1964292"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00182-4"},{"key":"e_1_3_2_1_3_1","volume-title":"ITP 2016, Nancy, France, August 22--25, 2016, Proceedings (Lecture Notes in Computer Science), Jasmin Christian Blanchette and Stephan Merz (Eds.)","volume":"9807","author":"Ausaf Fahad","year":"2016","unstructured":"Fahad Ausaf , Roy Dyckhoff , and Christian Urban . 2016 . POSIX Lexing with Derivatives of Regular Expressions (Proof Pearl). In Interactive Theorem Proving - 7th International Conference , ITP 2016, Nancy, France, August 22--25, 2016, Proceedings (Lecture Notes in Computer Science), Jasmin Christian Blanchette and Stephan Merz (Eds.) , Vol. 9807 . Springer, 69--86. Fahad Ausaf, Roy Dyckhoff, and Christian Urban. 2016. POSIX Lexing with Derivatives of Regular Expressions (Proof Pearl). In Interactive Theorem Proving - 7th International Conference, ITP 2016, Nancy, France, August 22--25, 2016, Proceedings (Lecture Notes in Computer Science), Jasmin Christian Blanchette and Stephan Merz (Eds.), Vol. 9807. Springer, 69--86."},{"key":"e_1_3_2_1_4_1","volume-title":"Certified Context-Free Parsing: A formalisation of Valiant's Algorithm in Agda. CoRR abs\/1601.07724","author":"Bernardy Jean-Philippe","year":"2016","unstructured":"Jean-Philippe Bernardy and Patrik Jansson . 2016. Certified Context-Free Parsing: A formalisation of Valiant's Algorithm in Agda. CoRR abs\/1601.07724 ( 2016 ). http:\/\/arxiv.org\/abs\/1601.07724 Jean-Philippe Bernardy and Patrik Jansson. 2016. Certified Context-Free Parsing: A formalisation of Valiant's Algorithm in Agda. CoRR abs\/1601.07724 (2016). http:\/\/arxiv.org\/abs\/1601.07724"},{"key":"e_1_3_2_1_5_1","volume-title":"Interactive Theorem Proving and Program Development: Coq'Art The Calculus of Inductive Constructions","author":"Bertot Yves","unstructured":"Yves Bertot and Pierre Castran . 2010. Interactive Theorem Proving and Program Development: Coq'Art The Calculus of Inductive Constructions ( 1 st ed.). Springer Publishing Company, Inc orporated. Yves Bertot and Pierre Castran. 2010. Interactive Theorem Proving and Program Development: Coq'Art The Calculus of Inductive Constructions (1st ed.). Springer Publishing Company, Incorporated.","edition":"1"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1932681.1863585"},{"key":"e_1_3_2_1_8_1","volume-title":"David Van Horn, and Eight Students of Northeastern University","author":"Felleisen Matthias","year":"2013","unstructured":"Matthias Felleisen , M.D. Barski Conrad , David Van Horn, and Eight Students of Northeastern University . 2013 . Realm of Racket: Learn to Program, One Game at a Time! No Starch Press, San Francisco, CA, USA. Matthias Felleisen, M.D. Barski Conrad, David Van Horn, and Eight Students of Northeastern University. 2013. Realm of Racket: Learn to Program, One Game at a Time! No Starch Press, San Francisco, CA, USA."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03545-1_7"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlamp.2014.09.002"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlamp.2014.09.002"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863543.1863594"},{"key":"e_1_3_2_1_13_1","volume-title":"31st International Colloquium, ICALP 2004, Turku, Finland, July 12--16, 2004. Proceedings (Lecture Notes in Computer Science), Josep D\u00edaz, Juhani Karhum\u00e4ki, Arto Lepist\u00f6, and Donald Sannella (Eds.)","volume":"3142","author":"Frisch Alain","year":"2004","unstructured":"Alain Frisch and Luca Cardelli . 2004 . Greedy Regular Expression Matching. In Automata, Languages and Programming : 31st International Colloquium, ICALP 2004, Turku, Finland, July 12--16, 2004. Proceedings (Lecture Notes in Computer Science), Josep D\u00edaz, Juhani Karhum\u00e4ki, Arto Lepist\u00f6, and Donald Sannella (Eds.) , Vol. 3142 . Springer, 618--629. Alain Frisch and Luca Cardelli. 2004. Greedy Regular Expression Matching. In Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12--16, 2004. Proceedings (Lecture Notes in Computer Science), Josep D\u00edaz, Juhani Karhum\u00e4ki, Arto Lepist\u00f6, and Donald Sannella (Eds.), Vol. 3142. Springer, 618--629."},{"key":"e_1_3_2_1_14_1","unstructured":"Grep 2017. GNU Grep home page. https:\/\/www.gnu.org\/software\/grep\/. (2017).  Grep 2017. GNU Grep home page. https:\/\/www.gnu.org\/software\/grep\/. (2017)."},{"key":"e_1_3_2_1_15_1","unstructured":"Happy 2001. Happy: The parser generator for Haskell. http:\/\/www.haskell.org\/happy (2001).  Happy 2001. Happy: The parser generator for Haskell. http:\/\/www.haskell.org\/happy (2001)."},{"key":"e_1_3_2_1_16_1","volume-title":"Ullman","author":"Hopcroft John E.","year":"2000","unstructured":"John E. Hopcroft , Rajeev Motwani , Rotwani, and Jeffrey D . Ullman . 2000 . Introduction to Automata Theory, Languages and Computability (2nd ed.). Addison-Wesley Longman Publishing Co. , Inc., Boston, MA, USA. John E. Hopcroft, Rajeev Motwani, Rotwani, and Jeffrey D. Ullman. 2000. Introduction to Automata Theory, Languages and Computability (2nd ed.). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28869-2_20"},{"key":"e_1_3_2_1_18_1","unstructured":"M. E. Lesk and E. Schmidt. 1990. UNIX Vol. II. W. B. Saunders Company Philadelphia PA USA Chapter Lex&Mdash;a Lexical Analyzer Generator 375--387. http:\/\/dl.acm.org\/citation.cfm?id=107172.107193   M. E. Lesk and E. Schmidt. 1990. UNIX Vol. II. W. B. Saunders Company Philadelphia PA USA Chapter Lex&Mdash;a Lexical Analyzer Generator 375--387. http:\/\/dl.acm.org\/citation.cfm?id=107172.107193"},{"key":"e_1_3_2_1_19_1","volume-title":"Programming Languages --- Lecture Notes in Computer Science 9889","author":"Lopes Raul","unstructured":"Raul Lopes , Rodrigo Ribeiro , and Carlos Camar\u00e3o . 2015. Certified Derivative-Based Parsing of Regular Expressions . In Programming Languages --- Lecture Notes in Computer Science 9889 . Springer , 95--109. Raul Lopes, Rodrigo Ribeiro, and Carlos Camar\u00e3o. 2015. Certified Derivative-Based Parsing of Regular Expressions. In Programming Languages --- Lecture Notes in Computer Science 9889. Springer, 95--109."},{"key":"e_1_3_2_1_20_1","volume-title":"Typing linear algebra: A biproduct-oriented approach. CoRR abs\/1312.4818","author":"Macedo Hugo Daniel","year":"2013","unstructured":"Hugo Daniel Macedo and Jos\u00e9 Nuno Oliveira . 2013. Typing linear algebra: A biproduct-oriented approach. CoRR abs\/1312.4818 ( 2013 ). http:\/\/arxiv.org\/abs\/1312.4818 Hugo Daniel Macedo and Jos\u00e9 Nuno Oliveira. 2013. Typing linear algebra: A biproduct-oriented approach. CoRR abs\/1312.4818 (2013). http:\/\/arxiv.org\/abs\/1312.4818"},{"key":"e_1_3_2_1_21_1","volume-title":"Twenty-five years of constructive type theory (Venice","author":"Martin-L\u00f6f Per","year":"1995","unstructured":"Per Martin-L\u00f6f . 1998. An intuitionistic theory of types . In Twenty-five years of constructive type theory (Venice , 1995 ). Oxford Logic Guides, Vol . 36. Oxford Univ. Press , New York, 127--172. Per Martin-L\u00f6f. 1998. An intuitionistic theory of types. In Twenty-five years of constructive type theory (Venice, 1995). Oxford Logic Guides, Vol. 36. Oxford Univ. Press, New York, 127--172."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796803004829"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2034574.2034801"},{"key":"e_1_3_2_1_24_1","volume-title":"Bit-coded Regular Expression Parsing","author":"Nielsen Lasse","unstructured":"Lasse Nielsen and Fritz Henglein . 2011. Bit-coded Regular Expression Parsing . Springer Berlin Heidelberg , Berlin, Heidelberg , 402--413. Lasse Nielsen and Fritz Henglein. 2011. Bit-coded Regular Expression Parsing. Springer Berlin Heidelberg, Berlin, Heidelberg, 402--413."},{"key":"e_1_3_2_1_25_1","volume-title":"Paulson","author":"Nipkow Tobias","year":"2002","unstructured":"Tobias Nipkow , Markus Wenzel , and Lawrence C . Paulson . 2002 . Isabelle\/HOL: A Proof Assistant for Higher-order Logic. Springer-Verlag , Berlin, Heidelberg. Tobias Nipkow, Markus Wenzel, and Lawrence C. Paulson. 2002. Isabelle\/HOL: A Proof Assistant for Higher-order Logic. Springer-Verlag, Berlin, Heidelberg."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1481861.1481862"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796808007090"},{"key":"e_1_3_2_1_28_1","unstructured":"re2 2016. Google Regular Expression Library - re2. https:\/\/github.com\/google\/re2. (2016).  re2 2016. Google Regular Expression Library - re2. https:\/\/github.com\/google\/re2. (2016)."},{"key":"e_1_3_2_1_29_1","unstructured":"Rodrigo Ribeiro Raul Lopes and Carlos Camar\u00e3o. 2017. Certified Derivative Based Parsing of Regular Expressions --- On-line repository. https:\/\/github.com\/rodrigogribeiro\/regex. (2017).  Rodrigo Ribeiro Raul Lopes and Carlos Camar\u00e3o. 2017. Certified Derivative Based Parsing of Regular Expressions --- On-line repository. https:\/\/github.com\/rodrigogribeiro\/regex. (2017)."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25379-9_10"},{"key":"e_1_3_2_1_31_1","volume-title":"Lectures on the Curry-Howard Isomorphism","author":"S\u00f8rensen Morten Heine","unstructured":"Morten Heine S\u00f8rensen and Pawel Urzyczyn . 2006. Lectures on the Curry-Howard Isomorphism , Volume 149 (Studies in Logic and the Foundations of Mathematics). Elsevier Science Inc ., New York, NY, USA. Morten Heine S\u00f8rensen and Pawel Urzyczyn. 2006. Lectures on the Curry-Howard Isomorphism, Volume 149 (Studies in Logic and the Foundations of Mathematics). Elsevier Science Inc., New York, NY, USA."},{"key":"e_1_3_2_1_32_1","volume-title":"Verified Functional Programming in Agda","author":"Stump Aaron","unstructured":"Aaron Stump . 2016. Verified Functional Programming in Agda . Association for Computing Machinery and Morgan ; Claypool, New York, NY, USA. Aaron Stump. 2016. Verified Functional Programming in Agda. Association for Computing Machinery and Morgan; Claypool, New York, NY, USA."},{"key":"e_1_3_2_1_33_1","volume-title":"FLOPS 2014, Kanazawa, Japan, June 4--6, 2014. Proceedings (Lecture Notes in Computer Science), Michael Codish and Eijiro Sumii (Eds.)","volume":"8475","author":"Sulzmann Martin","year":"2014","unstructured":"Martin Sulzmann and Kenny Zhuo Ming Lu . 2014 . POSIX Regular Expression Parsing with Derivatives. In Functional and Logic Programming - 12th International Symposium , FLOPS 2014, Kanazawa, Japan, June 4--6, 2014. Proceedings (Lecture Notes in Computer Science), Michael Codish and Eijiro Sumii (Eds.) , Vol. 8475 . Springer, 203--220. Martin Sulzmann and Kenny Zhuo Ming Lu. 2014. POSIX Regular Expression Parsing with Derivatives. In Functional and Logic Programming - 12th International Symposium, FLOPS 2014, Kanazawa, Japan, June 4--6, 2014. Proceedings (Lecture Notes in Computer Science), Michael Codish and Eijiro Sumii (Eds.), Vol. 8475. Springer, 203--220."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80046-8"}],"event":{"name":"SBLP 2017: 21st Brazilian Symposium on Programming Languages","location":"Fortaleza CE Brazil","acronym":"SBLP 2017","sponsor":["SBC Brazilian Computer Society","CNPq Conselho Nacional de Desenvolvimento Cientifico e Tecn","CAPES Brazilian Higher Education Funding Council"]},"container-title":["Proceedings of the 21st Brazilian Symposium on Programming Languages"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3125374.3125381","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3125374.3125381","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:23Z","timestamp":1750212683000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3125374.3125381"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,21]]},"references-count":34,"alternative-id":["10.1145\/3125374.3125381","10.1145\/3125374"],"URL":"https:\/\/doi.org\/10.1145\/3125374.3125381","relation":{},"subject":[],"published":{"date-parts":[[2017,9,21]]},"assertion":[{"value":"2017-09-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}