SPLASH 2025
Sun 12 - Sat 18 October 2025 Singapore
co-located with ICFP/SPLASH 2025
Tue 14 Oct 2025 15:00 - 15:20 at Orchid East - Abstract Interpretation Chair(s): Marco Campion

Runtime efficiency and termination are crucial properties in the studies of program verification. Instead of dealing with these issues in an ad hoc manner, it would be useful to develop a robust framework in which such properties are guaranteed by design. This paper introduces a new imperative programming language whose design is grounded in a static type system that ensures the following equivalence property: All definable programs are guaranteed to run in polynomial time; Conversely, all problems solvable in polynomial time can be solved by some programs of the language. The contribution of this work is twofold. On the theoretical side, the foundational equivalence property is established, and the proof of the equivalence theorem is non-trivial. On the practical side, a programming approach is proposed that can streamline program analysis and verification for feasible computations. An interpreter for the language has been implemented, demonstrating the feasibility of the approach in practice.

Tue 14 Oct

Displayed time zone: Perth change

13:40 - 15:20
Abstract InterpretationSAS at Orchid East
Chair(s): Marco Campion Sorbonne Université
13:40
60m
Keynote
Towards static analyses and abstract domains for hyperproperties
SAS
Xavier Rival Inria - CNRS - Ecole Normale Superieure de Paris - PSL University
14:40
20m
Talk
Comparing the Precision of Abstract Operators in the eBPF Verifier using Differential Synthesis
SAS
Link to publication Pre-print
15:00
20m
Talk
A Programming Language for Feasible Solutions
SAS
Weijun Chen Shanghai Jiao Tong University, China, Yuxi Fu Shanghai Jiao Tong University, China, Huan Long Shanghai Jiao Tong University