Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with binary decision diagrams:
TR94-026 | 12th December 1994
Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener

On the Power of Different Types of Restricted Branching Programs

Almost the same types of restricted branching programs (or
binary decision diagrams BDDs) are considered in complexity
theory and in applications like hardware verification. These
models are read-once branching programs (free BDDs) and certain
types of oblivious branching programs (ordered and indexed BDDs
with k layers). The complexity of ... more >>>

TR95-042 | 14th September 1995
Beate Bollig, Ingo Wegener

Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams

Computational complexity is concerned with the complexity of solving
problems and computing functions and not with the complexity of verifying
circuit designs.
The importance of formal circuit verification is evident.
Therefore, a framework of a complexity theory for formal circuit
verification with binary decision diagrams ... more >>>

TR95-047 | 5th October 1995
Martin Loebbing, Ingo Wegener

The Number of Knight's Tours Equals 33,439,123,484,294 -- Counting with Binary Decision Diagrams

An increasing number of results in graph theory, combinatorics and
theoretical computer science is obtained with the help of computers,
e.g. the proof of the Four Colours Theorem or the computation of
certain Ramsey numbers. Binary decision diagrams, known as tools in
hardware verification ... more >>>

TR99-019 | 7th June 1999
Detlef Sieling

Lower Bounds for Linear Transformed OBDDs and FBDDs

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 ... more >>>

TR00-052 | 3rd July 2000
Beate Bollig, Ingo Wegener

Approximability and Nonapproximability by Binary Decision Diagrams

Many BDD (binary decision diagram) models are motivated
by CAD applications and have led to complexity theoretical
problems and results. Motivated by applications in genetic
programming Krause, Savick\'y, and Wegener (1999) have shown
that for the inner product function IP$_n$ and the direct
storage access function DSA$_n$ ... more >>>

TR01-073 | 24th October 2001
Beate Bollig, Philipp Woelfel, Stephan Waack

Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

Revisions: 1

Branching programs are a well-established computation model
for Boolean functions, especially read-once branching programs
have been studied intensively. Exponential lower bounds for
deterministic and nondeterministic read-once branching programs
are known for a long time. On the other hand, the problem of
proving superpolynomial lower bounds ... more >>>

TR03-061 | 29th August 2003
Jan Kára, Daniel Král

Free Binary Decision Diagrams for Computation of EAR_n

Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with a constraint (additional to binary decision diagrams) that each variable is tested at most once during the computation. The function EAR_n is the following Boolean function defined
for n x n Boolean matrices: EAR_n(M)=1 iff the matrix ... more >>>

TR11-041 | 24th March 2011
Dana Ron, Gilad Tsur

Testing Computability by Width-Two OBDDs

Property testing is concerned with deciding whether an object
(e.g. a graph or a function) has a certain property or is ``far''
(for a prespecified distance measure) from every object with
that property. In this work we consider the property of being
computable by a read-once ... more >>>

TR15-048 | 14th February 2015
Kamil Khadiev

Width Hierarchy for $k$-OBDD of Small Width

Revisions: 1

In this paper was explored well known model $k$-OBDD. There are proven width based hierarchy of classes of boolean functions which computed by $k$-OBDD. The proof of hierarchy is based on sufficient condition of Boolean function's non representation as $k$-OBDD and complexity properties of Boolean
function SAF. This function is ... more >>>

ISSN 1433-8092 | Imprint