All reports by Author Beate Bollig:

__
TR14-167
| 11th November 2014
__

Beate Bollig#### On the Minimization of (Complete) Ordered Binary Decision Diagrams

__
TR08-056
| 22nd April 2008
__

Beate Bollig#### On the OBDD complexity of the most significant bit of integer multiplication

__
TR07-110
| 24th October 2007
__

Beate Bollig#### The Optimal Read-Once Branching Program Complexity for the Direct Storage Access Function

__
TR07-049
| 1st June 2007
__

Beate Bollig, Niko Range, Ingo Wegener#### Exact OBDD Bounds for some Fundamental Functions

__
TR02-033
| 11th June 2002
__

Beate Bollig#### A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs

__
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

__
TR00-052
| 3rd July 2000
__

Beate Bollig, Ingo Wegener#### Approximability and Nonapproximability by Binary Decision Diagrams

__
TR00-048
| 3rd July 2000
__

Beate Bollig#### Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

__
TR99-048
| 7th December 1999
__

Beate Bollig, Ingo Wegener#### Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems

__
TR95-042
| 14th September 1995
__

Beate Bollig, Ingo Wegener#### Read-once Projections and Formal Circuit Verification 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

Beate Bollig

Ordered binary decision diagrams (OBDDs) are a popular data structure for Boolean functions.

Some applications work with a restricted variant called complete OBDDs

which is strongly related to nonuniform deterministic finite automata.

One of its complexity measures is the width which has been investigated

in several areas in computer science ...
more >>>

Beate Bollig

Integer multiplication as one of the basic arithmetic functions has been

in the focus of several complexity theoretical investigations.

Ordered binary decision diagrams (OBDDs) are one of the most common

dynamic data structures for boolean functions.

Among the many areas of application are verification, model checking,

computer-aided design, relational algebra, ...
more >>>

Beate Bollig

Branching programs are computation models

measuring the space of (Turing machine) computations.

Read-once branching programs (BP1s) are the

most general model where each graph-theoretical path is the computation

path for some input. Exponential lower bounds on the size of read-once

branching programs are known since a long time. Nevertheless, there ...
more >>>

Beate Bollig, Niko Range, Ingo Wegener

Ordered binary decision diagrams (OBDDs) are nowadays the most common

dynamic data structure or representation type for Boolean functions.

Among the many areas of application are verification, model checking,

computer aided design, relational algebra, and symbolic graph algorithms.

Although many even exponential lower bounds on the OBDD size of Boolean ...
more >>>

Beate Bollig

Branching programs are a well-established computation

model for boolean functions, especially read-once

branching programs (BP1s) have been studied intensively.

A very simple function $f$ in $n^2$ variables is

exhibited such that both the function $f$ and its negation

$\neg f$ can be computed by $\Sigma^3_p$-circuits,

the ...
more >>>

Beate Bollig, Philipp Woelfel, Stephan Waack

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

Beate Bollig, Ingo Wegener

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

Beate Bollig

Branching programs are a well established computation model for

Boolean functions, especially read-once branching programs have

been studied intensively.

In this paper the expressive power of nondeterministic read-once

branching programs, i.e., the class of functions

representable in polynomial size, is investigated.

For that reason two restricted models of nondeterministic read-once

more >>>

Beate Bollig, Ingo Wegener

Ordered binary decision diagrams (OBDDs) are nowadays the

most common dynamic data structure or representation type

for Boolean functions. Among the many areas of application

are verification, model checking, and computer aided design.

For many functions it is easy to estimate the OBDD ...
more >>>

Beate Bollig, Ingo Wegener

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

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener

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