%0 Report %1 TR182 %A Kunjan, T. %A Hinsberger, Uwe %A Kolla, Reiner %C Department of Computer Science %D 1997 %K myown %N 182 %T Approximative Representation of boolean Functions by size controllable ROBDD's. %U http://www5.informatik.uni-wuerzburg.de/publications/techreports/tr182.ps.gz %X ROBDDs are a very popular datastructure for the representation and manipulation of boolean functions. They have tractable sizes for many boolean functions and come up with efficient algorithms for boolean operations. In the worst case however, size and time complexity grows exponentially when performing a polynomial number of operations. However, there are applications where an approximate knowledge about a boolean function like a lower or upper bound may be sufficient. In this paper we present a datastructure based on ROBDDs, that allows to trade space and time efficiency for precision. The basic extension is provided by the computation of least upper resp. greatest lower bounds of a boolean function under a size constraint for its ROBDD. As a first practical application we conclude some experimental results for the computation of local don't cares in combinational circuits.

@techreport{TR182, abstract = {ROBDDs are a very popular datastructure for the representation and manipulation of boolean functions. They have tractable sizes for many boolean functions and come up with efficient algorithms for boolean operations. In the worst case however, size and time complexity grows exponentially when performing a polynomial number of operations. However, there are applications where an approximate knowledge about a boolean function like a lower or upper bound may be sufficient. In this paper we present a datastructure based on ROBDDs, that allows to trade space and time efficiency for precision. The basic extension is provided by the computation of least upper resp. greatest lower bounds of a boolean function under a size constraint for its ROBDD. As a first practical application we conclude some experimental results for the computation of local don't cares in combinational circuits.}, added-at = {2015-06-18T10:00:28.000+0200}, address = {Department of Computer Science}, author = {Kunjan, T. and Hinsberger, Uwe and Kolla, Reiner}, biburl = {https://www.bibsonomy.org/bibtex/2e636413d5868266851a315e1317338ed/trcsuniwue}, interhash = {4a971eab1fae6cb976a207a6301f9163}, intrahash = {e636413d5868266851a315e1317338ed}, keywords = {myown}, month = {September}, number = 182, timestamp = {2015-06-18T10:00:28.000+0200}, title = {Approximative Representation of boolean Functions by size controllable ROBDD's.}, type = {Technical Report}, url = {http://www5.informatik.uni-wuerzburg.de/publications/techreports/tr182.ps.gz}, year = 1997 }