{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T13:39:23Z","timestamp":1743082763234,"version":"3.40.3"},"publisher-location":"Cham","reference-count":51,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031770180"},{"type":"electronic","value":"9783031770197"}],"license":[{"start":{"date-parts":[[2024,11,22]],"date-time":"2024-11-22T00:00:00Z","timestamp":1732233600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,11,22]],"date-time":"2024-11-22T00:00:00Z","timestamp":1732233600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-77019-7_3","type":"book-chapter","created":{"date-parts":[[2024,11,21]],"date-time":"2024-11-21T20:48:18Z","timestamp":1732222098000},"page":"43-61","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Well-Behaved (Co)algebraic Semantics of\u00a0Regular Expressions in\u00a0Dafny"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Zetzsche","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"R\u00f3\u017cowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,11,22]]},"reference":[{"key":"3_CR1","unstructured":"AWS encryption SDK for Dafny. https:\/\/github.com\/aws\/aws-encryption-sdk-dafny"},{"key":"3_CR2","unstructured":"Dafny blog. https:\/\/dafny.org\/blog\/"},{"key":"3_CR3","unstructured":"The dafny programming and verification language. https:\/\/dafny.org\/"},{"key":"3_CR4","unstructured":"Microsoft research. https:\/\/www.microsoft.com\/en-us\/research\/"},{"key":"3_CR5","doi-asserted-by":"publisher","unstructured":"Anderson, C.J., et al.: NetKAT: semantic foundations for networks. In: The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2014, San Diego, CA, USA, 20\u201321 January 2014, pp. 113\u2013126. ACM (2014). https:\/\/doi.org\/10.1145\/2535838.2535862","DOI":"10.1145\/2535838.2535862"},{"key":"3_CR6","unstructured":"Angus, A., Kozen, D.: Kleene algebra with tests and program schematology. Technical report, Cornell University (2002)"},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/978-3-319-43144-4_5","volume-title":"Interactive Theorem Proving","author":"F Ausaf","year":"2016","unstructured":"Ausaf, F., Dyckhoff, R., Urban, C.: POSIX lexing with derivatives of regular expressions (proof pearl). In: Blanchette, J.C., Merz, S. (eds.) ITP 2016. LNCS, vol. 9807, pp. 69\u201386. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-43144-4_5"},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/11804192_17","volume-title":"Formal Methods for Components and Objects","author":"M Barnett","year":"2006","unstructured":"Barnett, M., Chang, B.-Y.E., DeLine, R., Jacobs, B., Leino, K.R.M.: Boogie: a modular reusable verifier for object-oriented programs. In: de Boer, F.S., Bonsangue, M.M., Graf, S., de Roever, W.-P. (eds.) FMCO 2005. LNCS, vol. 4111, pp. 364\u2013387. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11804192_17"},{"issue":"6","key":"3_CR9","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1145\/1953122.1953145","volume":"54","author":"M Barnett","year":"2011","unstructured":"Barnett, M., F\u00e4hndrich, M., Leino, K.R.M., M\u00fcller, P., Schulte, W., Venter, H.: Specification and verification: the spec# experience. Commun. ACM 54(6), 81\u201391 (2011)","journal-title":"Commun. ACM"},{"key":"3_CR10","unstructured":"Barth, A., Kozen, D.: Equational verification of cache blocking in LU decomposition using kleene algebra with tests. Technical report, Cornell University (2002)"},{"key":"3_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-662-54434-1_5","volume-title":"Programming Languages and Systems","author":"JC Blanchette","year":"2017","unstructured":"Blanchette, J.C., Bouzy, A., Lochbihler, A., Popescu, A., Traytel, D.: Friends with benefits: implementing corecursion in foundational proof assistants. In: Yang, H. (ed.) ESOP 2017. LNCS, vol. 10201, pp. 111\u2013140. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-54434-1_5"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Blanchette, J.C., Popescu, A., Traytel, D.: Foundational extensible corecursion: a proof assistant perspective. In: Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming, pp. 192\u2013204 (2015)","DOI":"10.1145\/2784731.2784732"},{"issue":"4","key":"3_CR13","doi-asserted-by":"publisher","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 (JACM) 11(4), 481\u2013494 (1964)","journal-title":"J. ACM (JACM)"},{"key":"3_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1007\/978-3-031-27481-7_32","volume-title":"Formal Methods","author":"F Cassez","year":"2023","unstructured":"Cassez, F., Fuller, J., Ghale, M.K., Pearce, D.J., Quiles, H.M.: Formal and executable semantics of the ethereum virtual machine in dafny. In: Chechik, M., Katoen, J.P., Leucker, M. (eds.) FM 2023. LNCS, vol. 14000, pp. 571\u2013583. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-27481-7_32"},{"key":"3_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-642-03359-9_2","volume-title":"Theorem Proving in Higher Order Logics","author":"E Cohen","year":"2009","unstructured":"Cohen, E., Dahlweid, M., Hillebrand, M., Leinenbach, D., Moskal, M., Santen, T., Schulte, W., Tobies, S.: VCC: a practical system for verifying concurrent C. In: Berghofer, S., Nipkow, T., Urban, C., Wenzel, M. (eds.) TPHOLs 2009. LNCS, vol. 5674, pp. 23\u201342. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03359-9_2"},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-540-78800-3_24","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"L de Moura","year":"2008","unstructured":"de Moura, L., Bj\u00f8rner, N.: Z3: an efficient SMT solver. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 337\u2013340. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78800-3_24"},{"key":"3_CR17","doi-asserted-by":"publisher","unstructured":"Foster, N., Kozen, D., Milano, M., Silva, A., Thompson, L.: A coalgebraic decision procedure for NetKAT. In: Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015, Mumbai, India, 15\u201317 January 2015, pp. 343\u2013355. ACM (2015). https:\/\/doi.org\/10.1145\/2676726.2677011","DOI":"10.1145\/2676726.2677011"},{"key":"3_CR18","volume-title":"Mastering Regular Expressions","author":"JEF Friedl","year":"2006","unstructured":"Friedl, J.E.F.: Mastering Regular Expressions, 3rd edn. O\u2019Reilly Media, Sebastopol (2006)","edition":"3"},{"key":"3_CR19","unstructured":"Gumm, H.P.: Elements of the general theory of coalgebras (2000)"},{"issue":"10","key":"3_CR20","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1145\/363235.363259","volume":"12","author":"CAR Hoare","year":"1969","unstructured":"Hoare, C.A.R.: An axiomatic basis for computer programming. Commun. ACM 12(10), 576\u2013580 (1969). https:\/\/doi.org\/10.1145\/363235.363259","journal-title":"Commun. ACM"},{"issue":"7","key":"3_CR21","doi-asserted-by":"publisher","first-page":"1533","DOI":"10.1142\/S0129054111008866","volume":"22","author":"M Holzer","year":"2011","unstructured":"Holzer, M., Kutrib, M.: The complexity of regular(-like) expressions. Int. J. Found. Comput. Sci. 22(7), 1533\u20131548 (2011). https:\/\/doi.org\/10.1142\/S0129054111008866","journal-title":"Int. J. Found. Comput. Sci."},{"key":"3_CR22","unstructured":"Hopcroft, J.E., Karp, R.M.: A linear algorithm for testing equivalence of finite automata (1971). https:\/\/api.semanticscholar.org\/CorpusID:120207847"},{"key":"3_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/11780274_20","volume-title":"Algebra, Meaning, and Computation","author":"B Jacobs","year":"2006","unstructured":"Jacobs, B.: A bialgebraic review of deterministic automata, regular expressions and languages. In: Futatsugi, K., Jouannaud, J.-P., Meseguer, J. (eds.) Algebra, Meaning, and Computation. LNCS, vol. 4060, pp. 375\u2013404. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11780274_20"},{"key":"3_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/978-3-642-32784-1_7","volume-title":"Coalgebraic Methods in Computer Science","author":"B Jacobs","year":"2012","unstructured":"Jacobs, B., Silva, A., Sokolova, A.: Trace semantics via determinization. In: Pattinson, D., Schr\u00f6der, L. (eds.) CMCS 2012. LNCS, vol. 7399, pp. 109\u2013129. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32784-1_7"},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Kleene, S.: Representation of events in nerve nets and finite automata. Autom. Stud. 3 (1951)","DOI":"10.1515\/9781400882618-002"},{"issue":"2","key":"3_CR26","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1006\/INCO.1994.1037","volume":"110","author":"D Kozen","year":"1994","unstructured":"Kozen, D.: A completeness theorem for Kleene algebras and the algebra of regular events. Inf. Comput. 110(2), 366\u2013390 (1994). https:\/\/doi.org\/10.1006\/INCO.1994.1037","journal-title":"Inf. Comput."},{"issue":"3","key":"3_CR27","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1145\/256167.256195","volume":"19","author":"D Kozen","year":"1997","unstructured":"Kozen, D.: Kleene algebra with tests. ACM Trans. Program. Lang. Syst. 19(3), 427\u2013443 (1997). https:\/\/doi.org\/10.1145\/256167.256195","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"3_CR28","unstructured":"Kozen, D.: Automata on guarded strings and applications. Technical report, Cornell University (2001)"},{"key":"3_CR29","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/3-540-44957-4_38","volume-title":"Computational Logic \u2014 CL 2000","author":"D Kozen","year":"2000","unstructured":"Kozen, D., Patron, M.-C.: Certification of compiler optimizations using Kleene algebra with tests. In: Lloyd, J., et al. (eds.) CL 2000. LNCS (LNAI), vol. 1861, pp. 568\u2013582. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44957-4_38"},{"issue":"1","key":"3_CR30","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/S10817-011-9223-4","volume":"49","author":"A Krauss","year":"2012","unstructured":"Krauss, A., Nipkow, T.: Proof pearl: regular expression equivalence and relation algebra. J. Autom. Reason. 49(1), 95\u2013106 (2012). https:\/\/doi.org\/10.1007\/S10817-011-9223-4","journal-title":"J. Autom. Reason."},{"key":"3_CR31","unstructured":"Leino, K.R.M.: Dafny power user. https:\/\/leino.science\/dafny-power-user\/"},{"key":"3_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/978-3-642-17511-4_20","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"KRM Leino","year":"2010","unstructured":"Leino, K.R.M.: Dafny: an automatic program verifier for functional correctness. In: Clarke, E.M., Voronkov, A. (eds.) LPAR 2010. LNCS, vol. 6355, pp. 348\u2013370. Springer, Cham (2010). https:\/\/doi.org\/10.1007\/978-3-642-17511-4_20"},{"key":"3_CR33","unstructured":"Leino, K.R.M.: Type-parameter completion (2019). https:\/\/leino.science\/papers\/krml270.html"},{"key":"3_CR34","unstructured":"Leino, K.R.M.: Iterating over a collection (2020). https:\/\/leino.science\/papers\/krml275.html"},{"key":"3_CR35","unstructured":"Leino, K.R.M.: Type-parameter modes: variance and cardinality preservation (2021). https:\/\/leino.science\/papers\/krml280.html"},{"key":"3_CR36","volume-title":"Program Proofs","author":"KRM Leino","year":"2023","unstructured":"Leino, K.R.M.: Program Proofs. MIT Press, Cambridge (2023)"},{"key":"3_CR37","unstructured":"Leino, K.R.M., Tristan, J.B.: Working with coinduction, extreme predicates, and ordinals (2023). https:\/\/leino.science\/papers\/krml285.html"},{"issue":"3","key":"3_CR38","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/j.jlamp.2014.12.004","volume":"84","author":"N Moreira","year":"2015","unstructured":"Moreira, N., Pereira, D., de Sousa, S.M.: Deciding Kleene algebra terms equivalence in coq. J. Log. Algebraic Methods Program. 84(3), 377\u2013401 (2015)","journal-title":"J. Log. Algebraic Methods Program."},{"key":"3_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/978-3-031-06773-0_23","volume-title":"NASA Formal Methods","author":"J Noble","year":"2022","unstructured":"Noble, J., Streader, D., Gariano, I.O., Samarakoon, M.: More programming than programming: teaching formal methods in a software engineering programme. In: Deshmukh, J.V., Havelund, K., Perez, I. (eds.) NFM 2022. LNCS, vol. 13260, pp. 431\u2013450. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-06773-0_23"},{"issue":"2","key":"3_CR40","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1017\/S0956796808007090","volume":"19","author":"S Owens","year":"2009","unstructured":"Owens, S., Reppy, J.H., Turon, A.: Regular-expression derivatives re-examined. J. Funct. Program. 19(2), 173\u2013190 (2009). https:\/\/doi.org\/10.1017\/S0956796808007090","journal-title":"J. Funct. Program."},{"key":"3_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1007\/BFB0012891","volume-title":"9th International Conference on Automated Deduction","author":"LC Paulson","year":"1988","unstructured":"Paulson, L.C.: Isabelle: The next seven hundred theorem provers. In: Lusk, E., Overbeek, R. (eds.) CADE 1988. LNCS, vol. 310, pp. 772\u2013773. Springer, Heidelberg (1988). https:\/\/doi.org\/10.1007\/BFB0012891"},{"key":"3_CR42","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-319-21401-6_15","volume-title":"Automated Deduction - CADE-25","author":"LC Paulson","year":"2015","unstructured":"Paulson, L.C.: A formalisation of finite automata using hereditarily finite sets. In: Felty, A.P., Middeldorp, A. (eds.) CADE 2015. LNCS (LNAI), vol. 9195, pp. 231\u2013245. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21401-6_15"},{"key":"3_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/978-3-642-37064-9_42","volume-title":"Language and Automata Theory and Applications","author":"J Rot","year":"2013","unstructured":"Rot, J., Bonsangue, M., Rutten, J.: Coinductive proof techniques for language equivalence. In: Dediu, A.-H., Mart\u00edn-Vide, C., Truthe, B. (eds.) LATA 2013. LNCS, vol. 7810, pp. 480\u2013492. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-37064-9_42"},{"issue":"1","key":"3_CR44","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(00)00056-6","volume":"249","author":"JJMM Rutten","year":"2000","unstructured":"Rutten, J.J.M.M.: Universal coalgebra: a theory of systems. Theoret. Comput. Sci. 249(1), 3\u201380 (2000). https:\/\/doi.org\/10.1016\/S0304-3975(00)00056-6","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR45","unstructured":"Silva, A.: Kleene coalgebra. Ph.D. thesis, University of Nijmegen (2010)"},{"key":"3_CR46","doi-asserted-by":"publisher","unstructured":"Smolka, S., Foster, N., Hsu, J., Kapp\u00e9, T., Kozen, D., Silva, A.: Guarded Kleene algebra with tests: verification of uninterpreted programs in nearly linear time. Proc. ACM Program. Lang. 4(POPL), 61:1\u201361:28 (2020). https:\/\/doi.org\/10.1145\/3371129","DOI":"10.1145\/3371129"},{"key":"3_CR47","unstructured":"Traytel, D.: Formal languages, formally and coinductively. Log. Methods Comput. Sci. 13 (2017)"},{"key":"3_CR48","unstructured":"Tristan, J.B., Leino, K.R.M.: AWS dafny training. https:\/\/dafny.org\/teaching-material\/"},{"key":"3_CR49","doi-asserted-by":"publisher","unstructured":"Turi, D., Plotkin, G.D.: Towards a mathematical operational semantics. In: Proceedings, 12th Annual IEEE Symposium on Logic in Computer Science, Warsaw, Poland, 29 June\u20132 July 1997. pp. 280\u2013291. IEEE Computer Society (1997). https:\/\/doi.org\/10.1109\/LICS.1997.614955","DOI":"10.1109\/LICS.1997.614955"},{"key":"3_CR50","unstructured":"Yang, Z., Wang, W., Casas, J., Cocchini, P., Yang, J.: Towards a correct-by-construction FHE model. Cryptology ePrint Archive (2023)"},{"key":"3_CR51","unstructured":"Zetzsche, S., R\u00f3\u017cowski, W.: Well-behaved (co)algebraic semantics of regular expressions in dafny (2024). https:\/\/dafny.org\/blog\/assets\/src\/semantics-of-regular-expressions\/Archive.zip"}],"container-title":["Lecture Notes in Computer Science","Theoretical Aspects of Computing \u2013 ICTAC 2024"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-77019-7_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,21]],"date-time":"2024-11-21T21:29:36Z","timestamp":1732224576000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-77019-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,22]]},"ISBN":["9783031770180","9783031770197"],"references-count":51,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-77019-7_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,11,22]]},"assertion":[{"value":"22 November 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that\u00a0are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"ICTAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Theoretical Aspects of Computing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bangkok","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Thailand","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 November 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 November 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ictac2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ictac2024.cs.ait.ac.th\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}