Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR99-019 | 7th June 1999 00:00

Lower Bounds for Linear Transformed OBDDs and FBDDs


Authors: Detlef Sieling
Publication: 9th June 1999 14:11
Downloads: 3012


Linear Transformed Ordered Binary Decision Diagrams (LTOBDDs) have
been suggested as a generalization of OBDDs for the representation and
manipulation of Boolean functions. Instead of variables as in the
case of OBDDs parities of variables may be tested at the nodes of an
LTOBDD. By this extension it is possible to represent functions in
polynomial size that do not have polynomial size OBDDs, e.g., the
characteristic functions of linear codes. In this paper lower bound
methods for LTOBDDs and some generalizations of LTOBDDs are presented
and applied to explicitly defined functions. By the lower bound
results it is possible to compare the set of functions with polynomial
size LTOBDDs and their generalizations with the set of functions with
polynomial size representations for many other restrictions of BDDs.

ISSN 1433-8092 | Imprint