Simplify: a theorem prover for program checking
David Detlefs, Greg Nelson, James B. Saxe · Journal of the ACM · 2005
This article provides a detailed description of the automatic theorem prover Simplify, which is the proof engine of the Extended Static Checkers ESC/Java and ESC/Modula-3. Simplify uses the Nelson--Oppen method to combine decision procedures for several important theories, and also employs a matcher to reason about quantifiers. Instead of conventional matching in a term DAG, Simplify matches up to equivalence in an E-graph, which detects many relevant pattern instances that would be missed by the conventional approach. The article describes two techniques, error context reporting and error localization, for helping the user to determine the reason that a false conjecture is false. The article includes detailed performance figures on conjectures derived from realistic program-checking problems.
Cited by 786 works. doi:10.1145/1066100.1066102
Authors
References
- The Art of Computer Programming
- Linear Programming and Extensions
- Efficiency of a Good But Not Linear Set Union Algorithm
- The art of computer programming. Vol.1: Fundamental algorithms
- Towards a Mathematical Science of Computation
- Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis
- Chaff
- An improved equivalence algorithm
- Automated Theorem Proving: A Logical Basis
- Extended static checking for Java