Shtrichman,Range allocation for equivalence logic, in

Abstract. The range allocation problem was recently introduced as part of an efficient decision procedure for deciding satisfiability of equivalence logic formulas with or without uninterpreted functions. These type of for-mulas are mainly used when proving equivalence or refinement between systems (hardware designs, compiler’s translation, etc). The problem is to find in polynomial time a small finite domain for each of the variables in an equality formula ϕ, such that ϕ is valid if and only if it is valid over this small domain. The heuristic that was presented for finding small domains was static, i.e. it finds a small set of integer constants for each variable. In this paper we show new, more flexible range allocation meth-ods. We also show the limitations of these and other related approaches by proving a lower bound on the size of the state space generated by such procedures. To prove this lower bound we reduce the question to a graph theoretic counting question, which we believe to be of independent interest.