Fri 19 Jun 2026 14:00 - 14:20 at Flatirons 2 - Verification and Proof Reasoning Chair(s): Qianchuan Ye

Formally specifying, let alone verifying, properties of systems involving multiple programming languages is inherently challenging. We introduce <i>Heterogeneous Dynamic Logic</i> (HDL), a framework for combining reasoning principles from distinct (dynamic) program logics in a modular and compositional way. HDL mirrors the architecture of satisfiability modulo theories (SMT): Individual dynamic logics, along with their calculi, are treated as <i>dynamic theories</i> that can be combined to reason about heterogeneous systems whose components are verified using different program logics. HDL provides two key operations: <i>Lifting</i> extends an individual dynamic theory with new program constructs (e.g., the havoc operation or regular programs) and automatically augments its calculus with sound reasoning principles for the new constructs; and <i>Combination</i> enables cross-language reasoning in a <i>single modality</i> via <i>Heterogeneous Dynamic Theories</i>, facilitating the reuse of existing proof infrastructure. By lifting combined theories with regular programs, we obtain <i>heterogeneous</i> control structures that allow us to reason about intertwined cross-language behavior. We formalize dynamic theories, their lifting and combination, and prove the soundness of all proof rules in Isabelle. We also introduce a proof rule combining deductive DL-based reasoning with reasoning principles from Kleene Algebras with Tests. Furthermore, we prove <i>relative completeness</i> theorems for lifting and combination: Under usual assumptions, reasoning about lifted or combined theories is no harder than reasoning about the constituent dynamic theories and their common first-order structure (i.e., the data theory). We demonstrate HDL's value by verifying an automotive case study where a Java controller (formalized in Java dynamic logic) steers a plant model (formalized in differential dynamic logic).

Fri 19 Jun

Displayed time zone: Mountain Time (US & Canada) change

14:00 - 15:40
Verification and Proof ReasoningPLDI Research Papers at Flatirons 2
Chair(s): Qianchuan Ye University at Buffalo, SUNY
14:00
20m
Talk
Heterogeneous Dynamic Logic: Provability Modulo Program Theories
PLDI Research Papers
DOI
14:20
20m
Talk
Intrinsically Correct Algorithms and Recursive Coalgebras
PLDI Research Papers
Cass Alexandru RPTU Kaiserslautern-Landau & Radboud University Nijmegen, Henning Urbat Friedrich-Alexander University Erlangen-Nürnberg, Thorsten Wißmann Friedrich-Alexander University Erlangen-Nürnberg
DOI Pre-print
14:40
20m
Talk
CRIS: The Power of Imagination in Hybrid Verification
PLDI Research Papers
Yonghee Kim Seoul National University, Taeyoung Yoon Seoul National University, Sanghyun Yi Seoul National University, Jaehyung Lee Seoul National University, Soonwon Moon Seoul National University, Yeji Han Seoul National University, Seonho Lee Seoul National University, Taeyoung Rhee Seoul National University, Yujin Im Seoul National University, Donghyun Nam Seoul National University, Jieung Kim Yonsei University, Chung-Kil Hur Seoul National University
DOI
15:00
20m
Talk
Navigating AND–OR Graph Modifications to Debug Failing Proof Search
PLDI Research Papers
Justin Lubin University of California at Berkeley, Marlena Preigh University of California at Berkeley, Max Willsey University of California at Berkeley, Sarah E. Chasins University of California at Berkeley
DOI Pre-print
15:20
20m
Talk
[TOPLAS] Project Everest: Perspectives from Developing Industrial-Grade High-Assurance Software
PLDI Research Papers
Danel Ahman University of Tartu, Karthikeyan Bhargavan Cryspen, France, Barry Bond , Jay Bosamiya Microsoft Research, Christopher Brzuska , Antoine Delignat-Lavaud Microsoft Research, n.n., Cédric Fournet Microsoft Research, Aymeric Fromherz Inria, Sydney Gibson , Chris Hawblitzel Microsoft Research, Cătălin Hriţcu MPI-SP, Markulf Kohlweiss , Guido Martínez Microsoft Research, Haobin Ni University of Washington, Bryan Parno Carnegie Mellon University, Jonathan Protzenko Microsoft Azure Research, Tahina Ramananandro Microsoft Research, Aseem Rastogi Microsoft Research, Exequiel Rivas Tallinn University of Technology; Ahrefs, Nikhil Swamy Microsoft Research, Santiago Zanella-Béguelin Microsoft Research, Cambridge
Link to publication DOI