Relational String Abstract Domains

on YouTube ↗30m

" summary

Defines a constructive framework that turns any pre/partial string order into a relational abstract domain, instantiates it for substring, character inclusion and length orders, and proves soundness while leaving completeness open. Implements the r_sub domain inside a Go analyzer Galisa and composes it with the automata-based Tarsis (alphabet-of-strings automata). On top-10 GitHub string-heavy projects the reduced product keeps precision Tarsis alone misses and adds an average runtime overhead of <=3% (max 7%), showing practical gains.

AI-written summary · about

" chapters (16)

1. 0:00Introduction
2. 0:44Motivation
3. 2:13Relational Domains
4. 2:59Example
5. 4:14Goal
6. 7:27List Upper Bound
7. 9:21Abstract Semantics
8. 11:15Extraction Function
9. 15:17Extension
10. 16:47Implementation
11. 17:20Evaluation
12. 18:15Problem
13. 22:35Preliminary Evaluation
14. 23:28Conclusion
15. 24:20Future work
16. 25:45Questions