Accession Number : ADA135503

Title :   Simplification by Cooperating Decision Procedures,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Nelson,G ; Oppen,D C

PDF Url : ADA135503

Report Date : Apr 1978

Pagination or Media Count : 21

Abstract : This report describes a simplifier for use in program manipulation and verification. The simplifier finds a normal form for any expression over the language consisting of individual variables, the usual boolean connectives, equality, the conditional function cond (denoting if-then-else), the numerals, the arithmetic functions and predicates +, - and or=, the LISP constants, functions and predicates nil, car, cdr, cons and atom, the functions store and select for storing into and selecting from arrays, and uninterpreted function symbols. Individual variables range over the union of the reals, the set of arrays, LISP list structure and the booleans true and false. The simplifier is complete; that is, it simplifies every valid formula to true. Thus it is also a decision procedure for the quantifier-free theory of reals, arrays and list structure under the above functions and predicates. The organization of the simplifier is based on a method for combining decision procedures for several theories into a single decision procedure for a theory combining the original theories. More precisely, given a set S of functions and predicates over a fixed domain, a satisfiability program for S is a program which determines the satisfiability of conjunctions of literals (signed atomic formulas) whose predicate and function symbols are in S. We give a general procedure for combining satisfiability programs for sets S and T into a single satisfiability program for S u T, given certain conditions on S and T. The simplifier described in this paper is currently used in the Stanford Pascal Verifier.

Descriptors :   *Computer program verification, Computer logic, Simplification, Model theory, Decision making, Computations, Functions(Mathematics), Symbols, Symbolic programming, Arrays, Algorithms, Artificial intelligence, Computer programs

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE