Abstract Lipschitz Continuity
cs.PL
Submitted: 2026-10-27
Updated: 2026-10-27
License: http://creativecommons.org/licenses/by/4.0/
The gist: We introduce Abstract Lipschitz Continuity (ALC), an extensional property of functions, in particular of program semantics…
Abstract
We introduce Abstract Lipschitz Continuity (ALC), an extensional property of functions, in particular of program semantics, requiring that bounded differences between properties of two inputs yield proportionally bounded differences between properties of the corresponding outputs. ALC explicitly discerns between two complementary forms of approximation: property-based (or qualitative) approximations, which retain a property of the data and are formalized by upper closure operators as in abstract interpretation, and quantitative approximations, which measure the closeness of data and are formalized by pre-metrics, a weakening of metrics that covers the distances arising in program analysis. Keeping the two forms of approximation explicit has two main benefits. First, it allows us to precisely relate ALC to established extensional properties: ALC is a sufficient condition for partial completeness in abstract interpretation, for partial abstract non-interference in language-based security and, with a null Lipschitz constant, for abstract robustness in machine learning. Second, it supports reasoning about ALC of program semantics by induction on the syntax of programs: we present a sound deductive system, parametric in the property-based approximations and in the pre-metric of interest, that reduces a proof of ALC for a program to proofs for its basic commands and to some explicit side conditions, which isolate what makes ALC compositional across sequential composition, non-deterministic choice and iteration.
Related papers
- Formal Verification of an Out-of-Order Multiprocessor against an In-Order Weak-Memory ISA
- Fuss-free cumulative universes: theory and practice
- High-Level Synthesis of Efficient Pipelines with Visibility Control
- Model Checking Probabilistic Multiparty Session Types
- A Type System for Communication-Safe Hardware Design
- RECURSUM: Automated Code Generation for Recurrence Relations Exceeds Expert Optimization via LayeredCodegen