Translation of Temporal Logic for Efficient Infinite-State Reactive Synthesis

on YouTube ↗19m

" summary

Proposes a monitor with SMT-based invariants that keeps first-order and temporal structure during translation to symbolic games, emits four verdicts: unsafe/valid/safety/sufficient for finite prefixes, and uses those verdicts to prune states and simplify winning conditions. Prototype integrates Spot, Z3, MuAL and the POPL’24 game server, and on benchmarks the enriched product often yields much smaller games and faster solves (but adds overhead on trivial cases); artifacts and evaluations are available.

AI-written summary · about

" chapters (15)

1. 0:00Temporal logic translation
2. 0:27Infinite-state reactive synthesis
3. 1:31Program versus reactive synthesis
4. 2:34Temporal logic with data
5. 3:38Monitor-based approach
6. 4:42Reactive program LTL
7. 6:07Symbolic games translation
8. 7:30Monitor construction and theory
9. 8:35Monitor derivation example
10. 10:40Simplifying winning condition
11. 11:42Monitor and game product
12. 12:48Evaluation setup
13. 13:54Results and comparison
14. 14:36Conclusion
15. 15:18Q&A