FMCAD 2004 START ConferenceManager    


Variable Reuse for Efficient Image Computation

Zijiang Yang and Rajeev Alur

Presented at Formal Methods in Computer-Aided Design (FMCAD 2004), Austin, Texas, November 14-17, 2004


Abstract

Image computation, that is, computing the set of states reachable from a given set in one step, is a crucial component in typical tools for BDD-based symbolic reachability analysis. It has been shown that the size of the intermediate BDDs during image computation can be dramatically reduced via conjunctive partitioning of the transition relation and ordering the conjuncts for facilitating early quantification. In this paper, we propose to enhance the effectiveness of these techniques by reusing the quantified variables. Given an ordered set of conjuncts, if the last conjunct that uses a variable u appears before the first conjunct that uses another variable v, then v can be renamed to u, assuming u will be quantified immediately after its last use. In general, multiple variables can share the same identifier, and we give a polynomial-time algorithm for generating the optimum number of variables that are required for image computation. We show how to modify the image computation accounting for variable reuse, and demonstrate savings for image computation on ISCAS'89 and Texas'97 benchmark models.


  
START Conference Manager (V2.46.3)
Maintainer: sanders@cs.ubc.ca