An Algebra of Alignment for Relational Verification

on YouTube ↗25m

" summary

Extends Kleene Algebra with Tests into BiKAT and shows it exactly encodes lockstep and asynchronous product alignments so relational specs reduce to algebraic equations; proves an adequacy theorem that a bicat term covers all execution pairs, and gives a constructive equational method to build and check alignment products. Introduces forall-exists witnesses for forward/backward simulation, formalizes artifacts, notes the BiKAT equational theory is undecidable, and flags automation as open work.

AI-written summary · about

" chapters (9)

1. 0:00Start
2. 0:33Relational properties of programs
3. 1:20Establishing relational properties
4. 3:33Adequacy: covering all executions
5. 5:33Recall: Kleene Algebra with Tests (KAT)
6. 11:23Example revisited in BIKAT
7. 15:51Witness technique for V3 properties
8. 18:16Conclusion
9. 22:52Thm: forward simulation rules are derivable in BiKAT