期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：binary decision diagrams, branching programs, Linear Transformations, lower bounds
