© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Inferring Congruence Equations using SAT
Andy King and Harald Sondergaard
In Aarti Gupta and Sharad Malik, editors, Twentieth International Conference on Computer-Aided Verification, Lecture Notes in Computer Science, pages 182-196. Springer-Verlag, July 2008.Abstract
This paper proposes a new approach for deriving invariants that are systems of congruence equations where the modulo is a power of 2. The technique is an amalgam of SAT-solving, where a propositional formula is used to encode the semantics of a basic block, and abstraction, where the solutions to the formula are systematically combined and summarised as a system of congruence equations. The resulting technique is more precise than existing congruence analyses since a single optimal transfer function is derived for a basic block as a whole.
Download publication 222 kbytes (PDF)Bibtex Record
@inproceedings{2691, author = {Andy King and Harald S{o}ndergaard}, title = {Inferring {C}ongruence {E}quations using {SAT}}, month = {July}, year = {2008}, pages = {182-196}, keywords = {determinacy analysis, Craig interpolants}, note = {}, doi = {}, url = {http://www.cs.kent.ac.uk/pubs/2008/2691}, publication_type = {inproceedings}, submission_id = {841_1206970840}, booktitle = {Twentieth International Conference on Computer-Aided Verification}, editor = {Aarti Gupta and Sharad Malik}, series = {Lecture Notes in Computer Science}, publisher = {Springer-Verlag}, refereed = {yes}, }