{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T15:18:29Z","timestamp":1791299909392,"version":"4.1.0"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T00:00:00Z","timestamp":1673222400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-17-1-2787"],"award-info":[{"award-number":["N00014-17-1-2787"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSF","award":["CCF-2131476, CCF-2106845, CNS-1718713"],"award-info":[{"award-number":["CCF-2131476, CCF-2106845, CNS-1718713"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2023,1,9]]},"abstract":"<jats:p>Relational verification encompasses information flow security, regression verification, translation validation for compilers, and more. Effective alignment of the programs and computations to be related facilitates use of simpler relational invariants and relational procedure specs, which in turn enables automation and modular reasoning. Alignment has been explored in terms of trace pairs, deductive rules of relational Hoare logics (RHL), and several forms of product automata. This article shows how a simple extension of Kleene Algebra with Tests (KAT), called BiKAT, subsumes prior formulations, including alignment witnesses for forall-exists properties, which brings to light new RHL-style rules for such properties. Alignments can be discovered algorithmically or devised manually but, in either case, their adequacy with respect to the original programs must be proved; an explicit algebra enables constructive proof by equational reasoning. Furthermore our approach inherits algorithmic benefits from existing KAT-based techniques and tools, which are applicable to a range of semantic models.<\/jats:p>","DOI":"10.1145\/3571213","type":"journal-article","created":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T21:58:14Z","timestamp":1673474294000},"page":"573-603","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["An Algebra of Alignment for Relational Verification"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9654-4090","authenticated-orcid":false,"given":"Timos","family":"Antonopoulos","sequence":"first","affiliation":[{"name":"Yale University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7363-634X","authenticated-orcid":false,"given":"Eric","family":"Koskinen","sequence":"additional","affiliation":[{"name":"Stevens Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7628-8368","authenticated-orcid":false,"given":"Ton Chanh","family":"Le","sequence":"additional","affiliation":[{"name":"Stevens Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2779-2071","authenticated-orcid":false,"given":"Ramana","family":"Nagasamudram","sequence":"additional","affiliation":[{"name":"Stevens Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7634-6150","authenticated-orcid":false,"given":"David A.","family":"Naumann","sequence":"additional","affiliation":[{"name":"Stevens Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8484-1848","authenticated-orcid":false,"given":"Minh","family":"Ngo","sequence":"additional","affiliation":[{"name":"Stevens Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,1,11]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of LICS.","author":"Abadi Mart\u00edn","year":"1988","unstructured":"Mart\u00edn Abadi and Leslie Lamport . 1988 . The Existence of Refinement Mappings . In Proceedings of LICS. Mart\u00edn Abadi and Leslie Lamport. 1988. The Existence of Refinement Mappings. In Proceedings of LICS."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the ACM on Programming Languages, 3, OOPSLA","author":"Antonopoulos Timos","year":"2019","unstructured":"Timos Antonopoulos , Eric Koskinen , and Ton Chanh Le . 2019 . Specification and inference of trace refinement relations . Proceedings of the ACM on Programming Languages, 3, OOPSLA (2019), 1\u201330. Timos Antonopoulos, Eric Koskinen, and Ton Chanh Le. 2019. Specification and inference of trace refinement relations. Proceedings of the ACM on Programming Languages, 3, OOPSLA (2019), 1\u201330."},{"key":"e_1_2_1_3_1","volume-title":"Ramana Nagasamudram, David A. Naumann, and Minh Ngo.","author":"Antonopoulos Timos","year":"2022","unstructured":"Timos Antonopoulos , Eric Koskinen , Ton Chanh Le , Ramana Nagasamudram, David A. Naumann, and Minh Ngo. 2022 . An algebra of alignment for relational verification (extended version). CoRR , abs\/2202.04278 (2022), arXiv:2202.04278. arxiv:2202.04278 Timos Antonopoulos, Eric Koskinen, Ton Chanh Le, Ramana Nagasamudram, David A. Naumann, and Minh Ngo. 2022. An algebra of alignment for relational verification (extended version). CoRR, abs\/2202.04278 (2022), arXiv:2202.04278. arxiv:2202.04278"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.7144067"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84882-745-5"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368089.3409757"},{"key":"e_1_2_1_7_1","volume-title":"Naumann","author":"Banerjee Anindya","year":"2022","unstructured":"Anindya Banerjee , Ramana Nagasamudram , Mohammad Nikouei , and David A . Naumann . 2022 . A Relational Program Logic with Data Abstraction and Dynamic Framing. ACM Transactions on Programming Languages and Systems, Accepted for publication. Available as arxiv:1910.14560 Anindya Banerjee, Ramana Nagasamudram, Mohammad Nikouei, and David A. Naumann. 2022. A Relational Program Logic with Data Abstraction and Dynamic Framing. ACM Transactions on Programming Languages and Systems, Accepted for publication. Available as arxiv:1910.14560"},{"key":"e_1_2_1_8_1","volume-title":"Relational Logic with Framing and Hypotheses. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Long version at arxiv:1611","author":"Banerjee Anindya","year":"2016","unstructured":"Anindya Banerjee , David A. Naumann , and Mohammad Nikouei . 2016 . Relational Logic with Framing and Hypotheses. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Long version at arxiv:1611 .08992 Anindya Banerjee, David A. Naumann, and Mohammad Nikouei. 2016. Relational Logic with Framing and Hypotheses. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Long version at arxiv:1611.08992"},{"key":"e_1_2_1_9_1","volume-title":"Juan Manuel Crespo, and C\u00e9sar Kunz","author":"Barthe Gilles","year":"2011","unstructured":"Gilles Barthe , Juan Manuel Crespo, and C\u00e9sar Kunz . 2011 . Relational Verification Using Product Programs. In Formal Methods . Gilles Barthe, Juan Manuel Crespo, and C\u00e9sar Kunz. 2011. Relational Verification Using Product Programs. In Formal Methods."},{"key":"e_1_2_1_10_1","volume-title":"Juan Manuel Crespo, and C\u00e9sar Kunz","author":"Barthe Gilles","year":"2013","unstructured":"Gilles Barthe , Juan Manuel Crespo, and C\u00e9sar Kunz . 2013 . Beyond 2-Safety: Asymmetric Product Programs for Relational Program Verification. In Logical Foundations of Computer Science (LFCS) (LNCS , Vol. 7734). 29\u2013 43 . Gilles Barthe, Juan Manuel Crespo, and C\u00e9sar Kunz. 2013. Beyond 2-Safety: Asymmetric Product Programs for Relational Program Verification. In Logical Foundations of Computer Science (LFCS) (LNCS, Vol. 7734). 29\u201343."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlamp.2016.05.004"},{"key":"e_1_2_1_12_1","volume-title":"Secure Information Flow by Self-Composition","author":"Barthe Gilles","unstructured":"Gilles Barthe , Pedro R. D\u2019Argenio , and Tamara Rezk . 2004. Secure Information Flow by Self-Composition . In IEEE CSFW. See extended version BartheDR 11 Gilles Barthe, Pedro R. D\u2019Argenio, and Tamara Rezk. 2004. Secure Information Flow by Self-Composition. In IEEE CSFW. See extended version BartheDR11"},{"key":"e_1_2_1_13_1","volume-title":"Secure information flow by self-composition. Math. Struct. Comput. Sci., 21, 6","author":"Barthe Gilles","year":"2011","unstructured":"Gilles Barthe , Pedro R. D\u2019Argenio , and Tamara Rezk . 2011. Secure information flow by self-composition. Math. Struct. Comput. Sci., 21, 6 ( 2011 ). Gilles Barthe, Pedro R. D\u2019Argenio, and Tamara Rezk. 2011. Secure information flow by self-composition. Math. Struct. Comput. Sci., 21, 6 (2011)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Gilles Barthe Renate Eilers Pamina Georgiou Bernhard Gleiss Laura Kov\u00e1cs and Matteo Maffei. 2019. Verifying relational properties using trace logic. In 2019 Formal Methods in Computer Aided Design (FMCAD). 170\u2013178. \t\t\t\t  Gilles Barthe Renate Eilers Pamina Georgiou Bernhard Gleiss Laura Kov\u00e1cs and Matteo Maffei. 2019. Verifying relational properties using trace logic. In 2019 Formal Methods in Computer Aided Design (FMCAD). 170\u2013178.","DOI":"10.23919\/FMCAD.2019.8894277"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009896"},{"key":"e_1_2_1_16_1","volume-title":"Principled Software Development","author":"Beckert Bernhard","unstructured":"Bernhard Beckert and Mattias Ulbrich . 2018. Trends in relational program verification . In Principled Software Development . Springer , 41\u201358. Bernhard Beckert and Mattias Ulbrich. 2018. Trends in relational program verification. In Principled Software Development. Springer, 41\u201358."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"N. Benton. 2004. Simple Relational Correctness Proofs for Static Analyses and Program Transformations. In POPL. 14\u201325. \t\t\t\t  N. Benton. 2004. Simple Relational Correctness Proofs for Static Analyses and Program Transformations. In POPL. 14\u201325.","DOI":"10.1145\/982962.964003"},{"key":"e_1_2_1_18_1","volume-title":"Interactive Theorem Proving (ITP) (LNCS","author":"Beringer Lennart","year":"2011","unstructured":"Lennart Beringer . 2011 . Relational Decomposition . In Interactive Theorem Proving (ITP) (LNCS , Vol. 6898). Lennart Beringer. 2011. Relational Decomposition. In Interactive Theorem Proving (ITP) (LNCS, Vol. 6898)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-13185-1_17"},{"key":"e_1_2_1_20_1","volume-title":"International Conference on Interactive Theorem Proving. 163\u2013178","author":"Braibant Thomas","year":"2010","unstructured":"Thomas Braibant and Damien Pous . 2010 . An efficient Coq tactic for deciding Kleene algebras . In International Conference on Interactive Theorem Proving. 163\u2013178 . Thomas Braibant and Damien Pous. 2010. An efficient Coq tactic for deciding Kleene algebras. In International Conference on Interactive Theorem Proving. 163\u2013178."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Berkeley R. Churchill Oded Padon Rahul Sharma and Alex Aiken. 2019. Semantic program alignment for equivalence checking. In PLDI. \t\t\t\t  Berkeley R. Churchill Oded Padon Rahul Sharma and Alex Aiken. 2019. Semantic program alignment for equivalence checking. In PLDI.","DOI":"10.1145\/3314221.3314596"},{"key":"e_1_2_1_22_1","volume-title":"Principles of Security and Trust (POST) (LNCS","volume":"284","author":"Clarkson Michael R.","year":"2014","unstructured":"Michael R. Clarkson , Bernd Finkbeiner , Masoud Koleini , Kristopher K. Micinski , Markus N. Rabe , and C\u00e9sar S\u00e1nchez . 2014 . Temporal Logics for Hyperproperties . In Principles of Security and Trust (POST) (LNCS , Vol. 8414). 265\u2013 284 . Michael R. Clarkson, Bernd Finkbeiner, Masoud Koleini, Kristopher K. Micinski, Markus N. Rabe, and C\u00e9sar S\u00e1nchez. 2014. Temporal Logics for Hyperproperties. In Principles of Security and Trust (POST) (LNCS, Vol. 8414). 265\u2013284."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1891823.1891830"},{"key":"e_1_2_1_24_1","volume-title":"Proc. ACM Program. Lang., 4, POPL","author":"Clochard Martin","year":"2020","unstructured":"Martin Clochard , Claude March\u00e9 , and Andrei Paskevich . 2020 . Deductive Verification with Ghost Monitors . Proc. ACM Program. Lang., 4, POPL (2020). Martin Clochard, Claude March\u00e9, and Andrei Paskevich. 2020. Deductive Verification with Ghost Monitors. Proc. ACM Program. Lang., 4, POPL (2020)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/10722010_4"},{"key":"e_1_2_1_26_1","volume-title":"Concurrency Verification: Introduction to Compositional and Noncompositional Methods","author":"de Roever Willem-Paul","year":"2001","unstructured":"Willem-Paul de Roever , Frank de Boer , Ulrich Hannemann , Jozef Hooman , Yassine Lakhnech , Mannes Poel , and Job Zwiers . 2001 . Concurrency Verification: Introduction to Compositional and Noncompositional Methods . Cambridge University . Willem-Paul de Roever, Frank de Boer, Ulrich Hannemann, Jozef Hooman, Yassine Lakhnech, Mannes Poel, and Job Zwiers. 2001. Concurrency Verification: Introduction to Compositional and Noncompositional Methods. Cambridge University."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511663079"},{"key":"e_1_2_1_28_1","volume-title":"Foundations of Software Science and Computation Structures (FOSSACS) (LNCS","volume":"223","author":"Doumane Amina","year":"2019","unstructured":"Amina Doumane , Denis Kuperberg , Damien Pous , and Pierre Pradic . 2019 . Kleene Algebra with Hypotheses . In Foundations of Software Science and Computation Structures (FOSSACS) (LNCS , Vol. 11425). 207\u2013 223 . Amina Doumane, Denis Kuperberg, Damien Pous, and Pierre Pradic. 2019. Kleene Algebra with Hypotheses. In Foundations of Software Science and Computation Structures (FOSSACS) (LNCS, Vol. 11425). 207\u2013223."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563298"},{"key":"e_1_2_1_30_1","volume-title":"Modular Product Programs. In European Symposium on Programming.","author":"Eilers Marco","year":"2018","unstructured":"Marco Eilers , Peter M\u00fcller , and Samuel Hitz . 2018 . Modular Product Programs. In European Symposium on Programming. Marco Eilers, Peter M\u00fcller, and Samuel Hitz. 2018. Modular Product Programs. In European Symposium on Programming."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Azadeh Farzan and Anthony Vandikas. 2019. Automated hypersafety verification. In Computer Aided Verification. 200\u2013218. \t\t\t\t  Azadeh Farzan and Anthony Vandikas. 2019. Automated hypersafety verification. In Computer Aided Verification. 200\u2013218.","DOI":"10.1007\/978-3-030-25540-4_11"},{"key":"e_1_2_1_32_1","volume-title":"Symp. on Applied Math. 19","author":"Floyd Robert","year":"1967","unstructured":"Robert Floyd . 1967 . Assigning Meaning to Programs . In Symp. on Applied Math. 19 , Math. Aspects of Comp. Sci.. Amer. Math. Soc., 19\u201332. Robert Floyd. 1967. Assigning Meaning to Programs. In Symp. on Applied Math. 19, Math. Aspects of Comp. Sci.. Amer. Math. Soc., 19\u201332."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264278"},{"key":"e_1_2_1_34_1","volume-title":"Freyd and Andre Scedrov","author":"Peter","year":"1990","unstructured":"Peter J. Freyd and Andre Scedrov . 1990 . Categories, Allegories . North-Holland . Peter J. Freyd and Andre Scedrov. 1990. Categories, Allegories. North-Holland."},{"key":"e_1_2_1_35_1","volume-title":"ReLoC: A Mechanised Relational Logic for Fine-Grained Concurrency. In IEEE Symp. on Logic in Computer Science. 442\u2013451","author":"Frumin Dan","year":"2018","unstructured":"Dan Frumin , Robbert Krebbers , and Lars Birkedal . 2018 . ReLoC: A Mechanised Relational Logic for Fine-Grained Concurrency. In IEEE Symp. on Logic in Computer Science. 442\u2013451 . Dan Frumin, Robbert Krebbers, and Lars Birkedal. 2018. ReLoC: A Mechanised Relational Logic for Fine-Grained Concurrency. In IEEE Symp. on Logic in Computer Science. 442\u2013451."},{"key":"e_1_2_1_36_1","volume-title":"ReLoC Reloaded: A Mechanized Relational Logic for Fine-Grained Concurrency and Logical Atomicity. CoRR, abs\/2006.13635","author":"Frumin Dan","year":"2020","unstructured":"Dan Frumin , Robbert Krebbers , and Lars Birkedal . 2020. ReLoC Reloaded: A Mechanized Relational Logic for Fine-Grained Concurrency and Logical Atomicity. CoRR, abs\/2006.13635 ( 2020 ), arXiv:2006.13635. arxiv:2006.13635 Dan Frumin, Robbert Krebbers, and Lars Birkedal. 2020. ReLoC Reloaded: A Mechanized Relational Logic for Fine-Grained Concurrency and Logical Atomicity. CoRR, abs\/2006.13635 (2020), arXiv:2006.13635. arxiv:2006.13635"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-008-0075-2"},{"key":"#cr-split#-e_1_2_1_38_1.1","unstructured":"Manish Goyal Muqsit Azeem Kumar Madhukar and R. Venkatesh. 2021. Direct Construction of Program Alignment Automata for Equivalence Checking. https:\/\/doi.org\/10.48550\/ARXIV.2109.01864 10.48550\/ARXIV.2109.01864"},{"key":"#cr-split#-e_1_2_1_38_1.2","unstructured":"Manish Goyal Muqsit Azeem Kumar Madhukar and R. Venkatesh. 2021. Direct Construction of Program Alignment Automata for Equivalence Checking. https:\/\/doi.org\/10.48550\/ARXIV.2109.01864"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523722"},{"key":"e_1_2_1_40_1","volume-title":"Proc. ACM Program. Lang., 6, POPL","author":"G\u00e4her Lennard","year":"2022","unstructured":"Lennard G\u00e4her , Michael Sammler , Simon Spies , Ralf Jung , Hoang-Hai Dang , Robbert Krebbers , Jeehoon Kang , and Derek Dreyer . 2022 . Simuliris: a separation logic framework for verifying concurrent program optimizations . Proc. ACM Program. Lang., 6, POPL (2022). Lennard G\u00e4her, Michael Sammler, Simon Spies, Ralf Jung, Hoang-Hai Dang, Robbert Krebbers, Jeehoon Kang, and Derek Dreyer. 2022. Simuliris: a separation logic framework for verifying concurrent program optimizations. Proc. ACM Program. Lang., 6, POPL (2022)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Chris Hawblitzel Ming Kawaguchi Shuvendu K. Lahiri and Henrique Reb\u00ealo. 2013. Towards Modularly Comparing Programs Using Automated Theorem Provers. In CADE. 282\u2013299. \t\t\t\t  Chris Hawblitzel Ming Kawaguchi Shuvendu K. Lahiri and Henrique Reb\u00ealo. 2013. Towards Modularly Comparing Programs Using Automated Theorem Provers. In CADE. 282\u2013299.","DOI":"10.1007\/978-3-642-38574-2_20"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/27651.27653"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlamp.2015.09.012"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlamp.2019.05.005"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"M\u00e1t\u00e9 Kov\u00e1cs Helmut Seidl and Bernd Finkbeiner. 2013. Relational abstract interpretation for the verification of 2-hypersafety properties. In ACM Computer and Communications Security. \t\t\t\t  M\u00e1t\u00e9 Kov\u00e1cs Helmut Seidl and Bernd Finkbeiner. 2013. Relational abstract interpretation for the verification of 2-hypersafety properties. In ACM Computer and Communications Security.","DOI":"10.1145\/2508859.2516721"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/256167.256195"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/343369.343378"},{"key":"e_1_2_1_48_1","volume-title":"Kleene algebra with tests and the static analysis of programs","author":"Kozen Dexter","unstructured":"Dexter Kozen . 2003. Kleene algebra with tests and the static analysis of programs . Cornell University . Dexter Kozen. 2003. Kleene algebra with tests and the static analysis of programs. Cornell University."},{"key":"e_1_2_1_49_1","first-page":"1","article-title":"Some results in dynamic model theory. Sci","volume":"51","author":"Kozen Dexter","year":"2004","unstructured":"Dexter Kozen . 2004 . Some results in dynamic model theory. Sci . Comput. Program. , 51 , 1 - 2 (2004), 3\u201322. Dexter Kozen. 2004. Some results in dynamic model theory. Sci. Comput. Program., 51, 1-2 (2004), 3\u201322.","journal-title":"Comput. Program."},{"key":"e_1_2_1_50_1","volume-title":"International Workshop on Computer Science Logic. 244\u2013259","author":"Kozen Dexter","year":"1996","unstructured":"Dexter Kozen and Frederick Smith . 1996 . Kleene algebra with tests: Completeness and decidability . In International Workshop on Computer Science Logic. 244\u2013259 . Dexter Kozen and Frederick Smith. 1996. Kleene algebra with tests: Completeness and decidability. In International Workshop on Computer Science Logic. 244\u2013259."},{"key":"e_1_2_1_51_1","volume-title":"Verifying Hyperproperties With TLA. In IEEE Computer Security Foundations Symposium (CSF). 1\u201316","author":"Lamport Leslie","unstructured":"Leslie Lamport and Fred B. Schneider . 2021 . Verifying Hyperproperties With TLA. In IEEE Computer Security Foundations Symposium (CSF). 1\u201316 . Leslie Lamport and Fred B. Schneider. 2021. Verifying Hyperproperties With TLA. In IEEE Computer Security Foundations Symposium (CSF). 1\u201316."},{"key":"e_1_2_1_52_1","volume-title":"Proc. ACM Program. Lang., 4, POPL","author":"Maillard Kenji","year":"2020","unstructured":"Kenji Maillard , C\u0103t\u0103lin Hrit\u00e7u , Exequiel Rivas , and Antoine Van Muylder . 2020 . The Next 700 Relational Program Logics . Proc. ACM Program. Lang., 4, POPL (2020), 4:1\u20134:33. Kenji Maillard, C\u0103t\u0103lin Hrit\u00e7u, Exequiel Rivas, and Antoine Van Muylder. 2020. The Next 700 Relational Program Logics. Proc. ACM Program. Lang., 4, POPL (2020), 4:1\u20134:33."},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Konstantinos Mamouras. 2017. Equational Theories of Abnormal Termination Based on Kleene Algebra. In FoSSaCS. 88\u2013105. \t\t\t\t  Konstantinos Mamouras. 2017. Equational Theories of Abnormal Termination Based on Kleene Algebra. In FoSSaCS. 88\u2013105.","DOI":"10.1007\/978-3-662-54458-7_6"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.23919\/FMCAD.2019.8894274"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90227-X"},{"key":"e_1_2_1_56_1","volume-title":"Incorrect Implementation & More. CoRR, abs\/2003.04791","author":"Murray Toby","year":"2020","unstructured":"Toby Murray . 2020. An Under-Approximate Relational Logic: Heralding Logics of Insecurity , Incorrect Implementation & More. CoRR, abs\/2003.04791 ( 2020 ), arXiv:2003.04791. arxiv:2003.04791 Toby Murray. 2020. An Under-Approximate Relational Logic: Heralding Logics of Insecurity, Incorrect Implementation & More. CoRR, abs\/2003.04791 (2020), arXiv:2003.04791. arxiv:2003.04791"},{"key":"e_1_2_1_57_1","volume-title":"Alignment Completeness for Relational Hoare Logics. In IEEE Symp. on Logic in Computer Science. 1\u201313","author":"Nagasamudram Ramana","unstructured":"Ramana Nagasamudram and David A. Naumann . 2021 . Alignment Completeness for Relational Hoare Logics. In IEEE Symp. on Logic in Computer Science. 1\u201313 . Extended version at arxiv:2101.11730 Ramana Nagasamudram and David A. Naumann. 2021. Alignment Completeness for Relational Hoare Logics. In IEEE Symp. on Logic in Computer Science. 1\u201313. Extended version at arxiv:2101.11730"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-61470-6_7"},{"key":"e_1_2_1_59_1","volume-title":"Proceedings of the ACM on Programming Languages, 4, POPL","author":"O\u2019Hearn Peter W","year":"2019","unstructured":"Peter W O\u2019Hearn . 2019 . Incorrectness logic . Proceedings of the ACM on Programming Languages, 4, POPL (2019), 1\u201332. Peter W O\u2019Hearn. 2019. Incorrectness logic. Proceedings of the ACM on Programming Languages, 4, POPL (2019), 1\u201332."},{"key":"e_1_2_1_60_1","doi-asserted-by":"crossref","unstructured":"Lauren Pick Grigory Fedyukovich and Aarti Gupta. 2018. Exploiting Synchrony and Symmetry in Relational Verification. In Computer Aided Verification. 164\u2013182. \t\t\t\t  Lauren Pick Grigory Fedyukovich and Aarti Gupta. 2018. Exploiting Synchrony and Symmetry in Relational Verification. In Computer Aided Verification. 164\u2013182.","DOI":"10.1007\/978-3-319-96145-3_9"},{"key":"e_1_2_1_61_1","unstructured":"Damien Pous. [n. d.]. Relation Algebra and KAT in Coq. http:\/\/perso.ens-lyon.fr\/damien.pous\/ra\/ Coq library accessed July 2022 \t\t\t\t  Damien Pous. [n. d.]. Relation Algebra and KAT in Coq. http:\/\/perso.ens-lyon.fr\/damien.pous\/ra\/ Coq library accessed July 2022"},{"key":"e_1_2_1_62_1","volume-title":"ACM Symposium on Principles of Programming Languages. 357\u2013368","author":"Pous Damien","year":"2015","unstructured":"Damien Pous . 2015 . Symbolic algorithms for language equivalence and Kleene algebra with tests . In ACM Symposium on Principles of Programming Languages. 357\u2013368 . Damien Pous. 2015. Symbolic algorithms for language equivalence and Kleene algebra with tests. In ACM Symposium on Principles of Programming Languages. 357\u2013368."},{"key":"e_1_2_1_63_1","volume-title":"Relational and Algebraic Methods in Computer Science (RAMiCS) (LNCS","volume":"395","author":"Pous Damien","year":"2021","unstructured":"Damien Pous , Jurriaan Rot , and Jana Wagemaker . 2021 . On Tools for Completeness of Kleene Algebra with Hypotheses . In Relational and Algebraic Methods in Computer Science (RAMiCS) (LNCS , Vol. 13027). 378\u2013 395 . Damien Pous, Jurriaan Rot, and Jana Wagemaker. 2021. On Tools for Completeness of Kleene Algebra with Hypotheses. In Relational and Algebraic Methods in Computer Science (RAMiCS) (LNCS, Vol. 13027). 378\u2013395."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2002.806121"},{"key":"e_1_2_1_65_1","volume-title":"International Conference on Computer Aided Verification. 161\u2013179","author":"Shemer Ron","year":"2019","unstructured":"Ron Shemer , Arie Gurfinkel , Sharon Shoham , and Yakir Vizel . 2019 . Property directed self composition . In International Conference on Computer Aided Verification. 161\u2013179 . Ron Shemer, Arie Gurfinkel, Sharon Shoham, and Yakir Vizel. 2019. Property directed self composition. In International Conference on Computer Aided Verification. 161\u2013179."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908092"},{"key":"e_1_2_1_67_1","volume-title":"International Static Analysis Symposium. 352\u2013367","author":"Terauchi Tachio","year":"2005","unstructured":"Tachio Terauchi and Alex Aiken . 2005 . Secure information flow as a safety problem . In International Static Analysis Symposium. 352\u2013367 . Tachio Terauchi and Alex Aiken. 2005. Secure information flow as a safety problem. In International Static Analysis Symposium. 352\u2013367."},{"key":"e_1_2_1_68_1","doi-asserted-by":"crossref","unstructured":"Hiroshi Unno Tachio Terauchi and Eric Koskinen. 2021. Constraint-Based Relational Verification. In Computer Aided Verification. 742\u2013766. \t\t\t\t  Hiroshi Unno Tachio Terauchi and Eric Koskinen. 2021. Constraint-Based Relational Verification. In Computer Aided Verification. 742\u2013766.","DOI":"10.1007\/978-3-030-81685-8_35"},{"key":"e_1_2_1_69_1","volume-title":"Mathematics of Program Construction (LNCS","volume":"413","author":"Wagemaker Jana","year":"2019","unstructured":"Jana Wagemaker , Marcello M. Bonsangue , Tobias Kapp\u00e9 , Jurriaan Rot , and Alexandra Silva . 2019 . Completeness and Incompleteness of Synchronous Kleene Algebra . In Mathematics of Program Construction (LNCS , Vol. 11825). 385\u2013 413 . Jana Wagemaker, Marcello M. Bonsangue, Tobias Kapp\u00e9, Jurriaan Rot, and Alexandra Silva. 2019. Completeness and Incompleteness of Synchronous Kleene Algebra. In Mathematics of Program Construction (LNCS, Vol. 11825). 385\u2013413."},{"key":"e_1_2_1_70_1","volume-title":"Relational Separation Logic. Theo. Comp. Sci., 375","author":"Yang Hongseok","year":"2007","unstructured":"Hongseok Yang . 2007. Relational Separation Logic. Theo. Comp. Sci., 375 ( 2007 ). Hongseok Yang. 2007. Relational Separation Logic. Theo. Comp. Sci., 375 (2007)."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498690"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571213","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3571213","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:21Z","timestamp":1750183701000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571213"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,9]]},"references-count":72,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2023,1,9]]}},"alternative-id":["10.1145\/3571213"],"URL":"https:\/\/doi.org\/10.1145\/3571213","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,9]]},"assertion":[{"value":"2023-01-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}