CVC3

array_proof_rules.h

Go to the documentation of this file.
00001 /*****************************************************************************/
00002 /*!
00003  * \file array_proof_rules.h
00004  * 
00005  * Author: Clark Barrett 5/29/2003
00006  * 
00007  * Created: May 29 19:16:33 GMT 2003
00008  *
00009  * <hr>
00010  *
00011  * License to use, copy, modify, sell and/or distribute this software
00012  * and its documentation for any purpose is hereby granted without
00013  * royalty, subject to the terms and conditions defined in the \ref
00014  * LICENSE file provided with this distribution.
00015  * 
00016  * <hr>
00017  * 
00018  * CLASS: ArrayProofRules
00019  * 
00020  * 
00021  * Description: Array proof rules.
00022  */
00023 /*****************************************************************************/
00024 
00025 #ifndef _cvc3__theory_array__array_proof_rules_h_
00026 #define _cvc3__theory_array__array_proof_rules_h_
00027 
00028 #include <vector>
00029 
00030 namespace CVC3 {
00031 
00032   class Theorem;
00033   class Expr;
00034   
00035   class ArrayProofRules {
00036   public:
00037     // Destructor
00038     virtual ~ArrayProofRules() { }
00039 
00040     ////////////////////////////////////////////////////////////////////
00041     // Proof rules
00042     ////////////////////////////////////////////////////////////////////
00043 
00044     // ==>
00045     // write(store, index_0, v_0, index_1, v_1, ..., index_n, v_n) = store IFF
00046     //
00047     // read(store, index_n) = v_n &
00048     // index_{n-1} != index_n -> read(store, index_{n-1}) = v_{n-1} &
00049     // (index_{n-2} != index_{n-1} & index_{n-2} != index_n) -> read(store, index_{n-2}) = v_{n-2} &
00050     // ...
00051     // (index_1 != index_2 & ... & index_1 != index_n) -> read(store, index_1) = v_1
00052     // (index_0 != index_1 & index_0 != index_2 & ... & index_0 != index_n) -> read(store, index_0) = v_0
00053     virtual Theorem rewriteSameStore(const Expr& e, int n) = 0;
00054 
00055     // ==> write(store, index, value) = write(...) IFF
00056     //       store = write(write(...), index, read(store, index)) &
00057     //       value = read(write(...), index)
00058     virtual Theorem rewriteWriteWrite(const Expr& e) = 0;
00059 
00060     // ==> read(write(store, index1, value), index2) =
00061     //   ite(index1 = index2, value, read(store, index2))
00062     virtual Theorem rewriteReadWrite(const Expr& e) = 0;
00063 
00064     // e = read(write(store, index1, value), index2):
00065     // ==> ite(index1 = index2,
00066     //         read(write(store, index1, value), index2) = value,
00067     //         read(write(store, index1, value), index2) = read(store, index2))
00068     virtual Theorem rewriteReadWrite2(const Expr& e) = 0;
00069 
00070     // value = read(store, index) ==>
00071     //   write(store, index, value) = store
00072     virtual Theorem rewriteRedundantWrite1(const Theorem& v_eq_r,
00073              const Expr& write) = 0;
00074 
00075     // ==>
00076     //   write(write(store, index, v1), index, v2) = write(store, index, v2)
00077     virtual Theorem rewriteRedundantWrite2(const Expr& e) = 0;
00078 
00079     // ==>
00080     //   write(write(store, index1, v1), index2, v2) =
00081     //   write(write(store, index2, v2), index1, ite(index1 = index2, v2, v1))
00082     virtual Theorem interchangeIndices(const Expr& e) = 0;
00083     //! Beta reduction of array literal: |- (array x. f(x))[arg] = f(arg)
00084     virtual Theorem readArrayLiteral(const Expr& e) = 0;
00085 
00086     //! Lift ite over read
00087     virtual Theorem liftReadIte(const Expr& e) = 0;
00088 
00089     //! a /= b |- exists i. a[i] /= b[i]
00090     virtual Theorem arrayNotEq(const Theorem& e) = 0;
00091 
00092     virtual Theorem splitOnConstants(const Expr& a, const std::vector<Expr>& consts) = 0;
00093 
00094     virtual Theorem propagateIndexDiseq(const Theorem& read1eqread2isFalse) = 0;
00095 
00096   }; // end of class ArrayProofRules
00097 
00098 } // end of namespace CVC3
00099 
00100 #endif