Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
A Larger Lower Bound on the OBDD Complexity of the Most Significant Bit of Multiplication
verfasst von : Beate Bollig
Erschienen in: LATIN 2010: Theoretical Informatics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. The reachability problem, i.e., computing the set of nodes reachable from a predefined vertex
s
∈
V
in a digraph
G
= (
V
,
E
), is an important problem in computer-aided design, hardware verification, and model checking. Sawitzki (2006) has presented exponential lower bounds on the space complexity of a restricted class of symbolic OBDD-based algorithms for the reachability problem. Here, these lower bounds are improved by presenting a larger lower bound on the OBDD complexity of the most significant bit of integer multiplication.