Widening ROBDDs with Prime Implicants

Kettle, N. and King, A.M. and Strzemecki, T. (2006) Widening ROBDDs with Prime Implicants. In: Hermanns, H. and Palsberg, J., eds. Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science, 3920 . Springer-Verlag, Berlin, pp. 105-119. ISBN 978-3-540-33056-1.

Postscript
Download (460Kb)	Preview
Official URL http://dx.doi.org/10.1007/11691372_7

Abstract

Despite the ubiquity of ROBDDs in program analysis, and extensive literature on ROBDD minimisation, there is a dearth of work on approximating ROBDDs. The need for approximation arises because many ROBDD operations result in an ROBDD whose size is quadratic in the size of the inputs. Furthermore, if ROBDDs are used in abstract interpretation, the running time of the analysis is related not only to the complexity of the individual ROBDD operations but also the number of operations applied. The number of operations is, in turn, constrained by the number of times a Boolean function can be weakened before stability is achieved. This paper proposes a widening that can be used to both constrain the size of an ROBDD and also ensure that the number of times that it is weakened is bounded by some given constant. The widening can be used to either systematically approximate from above (i.e. derive a weaker function) or below (i.e. infer a stronger function).

Item Type:	Book section
Additional information:	Also see http://www.springer.de/comp/lncs/index.html
Uncontrolled keywords:	ROBDD, widening, approximation, abstract interpretation
Subjects:	Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions:	Faculties > Science Technology and Medical Studies > School of Computing > Theoretical Computing Group
Depositing User:	Mark Wheadon
Date Deposited:	24 Nov 2008 18:04
Last Modified:	30 Jul 2012 08:45
Resource URI:	http://kar.kent.ac.uk/id/eprint/14499 (The current URI for this page, for reference purposes)

• Depositors only (login required):