On the Monniaux Problem in Abstract Interpretation
The Monniaux Problem in abstract interpretation asks, roughly speaking, whether the following question is decidable: Given a program P , a safety (e.g., non-reachability) specification \(\varphi\) , and an abstract domain of invariants \(\mathcal {D}\) , does there exist an inductive invariant \(\mathcal {I}\) in \(\mathcal {D}\) guaranteeing that program P meets its specification φ? The Monniaux Problem is of course parameterised by the classes of programs and invariant domains that one considers. In this article, we show that the Monniaux Problem is undecidable for unguarded affine programs and semilinear invariants (unions of polyhedra). Moreover, we show that decidability is recovered in the important special case of simple linear loops.
Authors
- Nathanaël Fijalkow (ORCID: https://orcid.org/0000-0002-6576-4680)
- Pierre Ohlmann (ORCID: https://orcid.org/0000-0002-4685-5253)
- Engel Lefaucheux (ORCID: https://orcid.org/0000-0003-0875-300X)
- Joël Ouaknine (ORCID: https://orcid.org/0000-0003-0031-9356)
- James Worrell (ORCID: https://orcid.org/0000-0001-8151-2443)
- Amaury Pouly (ORCID: https://orcid.org/0000-0002-2549-951X)
Institutions
- Centre National de la Recherche Scientifique (FR)
- Université de Bordeaux (FR)
- University of Oxford (GB)
- Institut de Recherche en Informatique Fondamentale (FR)
- Max Planck Institute for Software Systems (DE)
- Laboratoire Bordelais de Recherche en Informatique (FR)
- Science Oxford (GB)
Publication Details
- Journal
- Journal of the ACM
- Published
- 2024-11-19
- DOI
- https://doi.org/10.1145/3704632
- Primary Topic
- Formal Methods in Verification
- Type
- article
- Field-Weighted Citation Impact
- 0.00