A proof-theoretic approach to abstract interpretation
Vijay D’Silva, Alessandra Palmigiano, Apostolos Tzimoulis, Caterina Urban · 2026
Read A proof-theoretic approach to abstract interpretation by Vijay D’Silva, Alessandra Palmigiano, Apostolos Tzimoulis, Caterina Urban (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-26591.txt.
Introduction
Vijay D'Silva and three colleagues build a proof-theoretic framework for abstract interpretation, pairing logics with finite abstractions. Building on work on abstraction logics, they propose a way to make a logic whose Lindenbaum-Tarski algebra matches a given abstract lattice. The approach finds connectives preserved by the concretization map, deriving proof rules. Soundness and completeness hold under conditions. The framework extends to Cartesian products and multi-part settings and probes octagon shapes. The authors suggest new links joining abstract interpretation, proof theory, and algebraic logic.
Catalog record
| CREATOR | Vijay D’Silva, Alessandra Palmigiano, Apostolos Tzimoulis, Caterina Urban |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 11473 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.26591
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A proof-theoretic approach to abstract interpretation Vijay D’Silva, Alessandra Palmigiano, Apostolos Tzimoulis, Caterina Urban Abstract 1 Introduction Abstract interpretation is a theory of formal program verification which generates sound approximations of the semantics of programs, and has been used as the basis of methods and effective algorithms to approximate undecidable or computationally intractable problems such as the verification of safety-critical software (e.g. medical, nuclear, aviation software). Typically, a complex concrete model (such as the powerset \mathcal{P}(\Sigma) of a possibly infinite set modelling program executions) is related to a model that can be efficiently represented and manipulated, which is usually a finite lattice A that encodes the relevant – logically interconnected – properties about these executions, by means of an adjoint pair of maps. Specifically, the right adjoint (the concretization map \gamma:A\to\mathcal{P}(\Sigma) ) provides the intended interpretation of the symbolic properties (that is, S\models a iff S\subseteq\gamma(a) for any S\in\mathcal{P}(\Sigma) and a\in A ); the left adjoint (the abstraction map \alpha:\mathcal{P}(\Sigma)\to A ) classifies the executions of the given program according to their satisfying the relevant properties. Even though the concrete model is usually a Boolean algebra, the algebraic structure that the abstract lattice A retains depends on the properties preserved by the concretization map \gamma . Although this theory was connected to logic since its inception [ 2 , 1 , 4 ] , it is only in the last decade that the connection was made systematic. In particular, the notion of an (internal) logic of an abstraction was introduced in [ 5 ] and systematically related to the order-theoretic properties of the concretization map. In [ 3 ] , this line of research is further developed. Namely, the logics underlying specific abstractions are identified, together with explicit specification of proof-theoretic presentations for each of them. The present note collects the preliminary results and observations of an ongoing work in which we generalise the results of [ 3 ] and introduce a general procedure for generating the (internal) logic of an abstraction together with the specification of a proof system for it. The main idea is to generate a logic whose Lindenbaum-Tarski algebra is isomorphic to the abstract algebra A . 2 Generating a logic corresponding to a finite abstraction We describe a general procedure for generating a logic \mathcal{L}_{A} with one variable corresponding to a finite abstraction \mathcal{A}=(A,\sqsubseteq,Op_{A}) with concretization \gamma:\mathcal{A}\to(P(\text{Struct}),\subseteq,Op_{c}) . 1. The logical connectives of the language of \mathcal{L}_{A} are the connectives preserved by \gamma . Notice that, whenever the finite abstraction \mathcal{A} is a distributive lattice, being finite, \mathcal{A} will be a bi-Heyting algebra. So in this case, the implication and the co-implication of the abstract lattice become available candidates as connectives of the language. 2. for every point a\in A , add a unary predicate symbol a(x) to the language; 3. for every connective that is preserved by \gamma , add the introduction rules appropriate to that connective in the proof system; 4. for every binary connective \star in \mathcal{L}_{A} and predicates a(x),b(x),c(x) such that a\star b=c , add a rule corresponding to the axiom a(x)\star b(x)\dashv\vdash c(x) in the proof system; 5. for every unary connective \star and predicates a(x) and b(x) such that \star a=b , add a rule corresponding to the axiom \star a(x)\dashv\vdash b(x) . 6. for all predicates a(x) and b(x) such that a\leq b , add a rule corresponding to the axiom a(x)\vdash b(x) . Lemma 1 . The logic \mathcal{L}_{A} is sound w.r.t. the concretization. Proof. The proof is by induction on the depth of the proof. The axioms are sound and the preservation of the connectives of \gamma guarantee that the introduction of the connectives are sound. Finally by the preservation of the connectives by \gamma and the definition of satisfaction of sequents in the concrete algebra (simply by verifying if the interpretation of the left hand side is included in the interpretation of the right hand side), the rules corresponding to the relationship between predicates described in items 4 and 5 are also sound. ∎ Let \mathbb{L} be the Lindenbaum-Tarski algebra of \mathcal{L}_{A} . Lemma 2 . The algebra \mathbb{L} is isomorphic to \mathcal{A} . Proof. Let e:\mathcal{A}\to\mathbb{L} be defined as e(a)=[a(x)] , where [a(x)] denotes the equivalence class of the predicate a(x) . First notice that e is surjective since each element in the Lindenbaum-Tarski algebra of the logic \mathcal{L}_{A} is the equivalence class of some predicate. This follows immediately by induction on the complexity of the formulas and items 4 and 5 in the construction. To show that e is injective let [a(x)]=[b(x)] . Then we have that a(x)\dashv\vdash b(x) . Notice that \mathcal{L}_{A} is sound w.r.t. \mathcal{A} when each predicate c(x) is interpreted as c . Hence, we immediately get that a=b . Finally, e being an order embedding and a homomorphism w.r.t. the connectives of the language follows immediately from items 4, 5 and 6, and the soundness of the logic w.r.t. \mathcal{A} . ∎ Lemma 3 . If \gamma is an order-embedding, then \mathcal{L}_{A} is complete w.r.t. the concretization. Proof. Let us assume that \gamma(a)\leq\gamma(b) and show that a(x)\vdash b(x) is derivable. Since \gamma is an order embedding, \gamma(a)\leq\gamma(b) implies that a\leq b . Then by item 6, a(x)\vdash b(x) is a rule of the proof system, and thus it is derivable. ∎ Notice that the lemma above strengthens [ 5 , Proposition 5] . Indeed, the statement of that proposition assumes \gamma to be an injective right adjoint, which implies but is not implied by the condition that \gamma is an order embedding. The above procedure is very naive: it is inefficient, since many axioms will be redundant, and it ignores computational limitations. However, it is applicable to any finite lattice \mathcal{A} and any concretization \gamma . 3 Cartesian products The proof theoretic analysis discussed in the previous section naturally generalizes to n variables. Indeed, formulas \varphi(\overline{x}) for \overline{x}=(x_{1},\ldots,x_{n}) can be interpreted on \wp(\mathbb{Z}^{n}) as \{\overline{a}\in\mathbb{Z}^{n}\mid\varphi(\overline{a})\} , and m such predicates \varphi_{1}(\overline{x}),\ldots,\varphi_{m}(\overline{x}) can be arranged into a finite lattice \mathbb{A} , such that the assignment \varphi(\overline{x})\mapsto\{\overline{a}\in\mathbb{Z}^{n}\mid\varphi(\overline{a})\} is an order embedding and provides the concretization map \gamma:\mathbb{A}\to\wp(\mathbb{Z}^{n}) . When \varphi_{i}(\overline{x})=\psi^{i}_{1}(x_{1})\land\cdots\land\psi^{i}_{n}(x_{n}) and \varphi_{i}(\overline{x})\vdash\varphi_{j}(\overline{x}) if and only if \psi^{i}_{k}(x_{k})\vdash\psi^{j}_{k}(x_{k}) for every 1\leq k\leq n , then \mathbb{A}=\prod_{1\leq k\leq n}\mathbb{A}_{k} , \gamma=\gamma^{\prime}\circ\iota where \iota:\wp(\mathbb{Z})^{n}\to\wp(\mathbb{Z}^{n}) is defined by the assignment (X_{1},\ldots,X_{n})\mapsto\prod_{1\leq k\leq n}X_{k} and \gamma^{\prime}=\prod_{1\leq k\leq n}\gamma_{k} with \gamma_{k}:\mathbb{A}_{k}\to\wp(\mathbb{Z}) and \psi^{k}_{j}(x_{k})\mapsto\{a\in\mathbb{Z}\mid\psi^{k}_{j}(a)\} . Intuitively, this means that \gamma(\varphi(\overline{x})) is an n -dimensional rectangle in \wp(\mathbb{Z}^{n}) . Notice that \iota has a left adjoint which assigns R\in\wp(\mathbb{Z}^{n}) to the smallest n -dimensional rectangle containing R . Hence, \iota always preserves all existing meets. Moreover, if (X_{1},\ldots,X_{n}) is such that X_{i}=\varnothing for some 1\leq i\leq n , then \iota(X_{1},\ldots,X_{n})=\varnothing . 4 On the logic of octagons We provide some observations on the logic of predicates of the form \pm x\pm y\geq c where c\in\mathbb{Z} is a constant. Let \mathcal{A} be the abstract algebra corresponding to these predicates and let \gamma:\mathcal{A}\to\wp(\mathbb{Z}\times\mathbb{Z}) be the concretization map. First of all we notice that \gamma preserves negation since \mathbb{Z}\times\mathbb{Z}\setminus\gamma(\pm x\pm y\geq c)=\gamma(\mp x\mp y\geq-c+1). On the other hand, it cannot preserve conjunction since there does not exist any of the above predicates that is satisfied by the same x,y such that x+y\geq