All reports by Author Detlef Sieling:

__
TR02-054
| 5th September 2002
__

Detlef Sieling#### Minimization of Decision Trees is Hard to Approximate

__
TR01-017
| 14th February 2001
__

Petr Savicky, Detlef Sieling#### A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism

__
TR99-019
| 7th June 1999
__

Detlef Sieling#### Lower Bounds for Linear Transformed OBDDs and FBDDs

__
TR99-001
| 4th January 1999
__

Detlef Sieling#### The Complexity of Minimizing FBDDs

Revisions: 1

__
TR98-045
| 17th July 1998
__

Detlef Sieling#### A Separation of Syntactic and Nonsyntactic (1,+k)-Branching Programs

__
TR98-001
| 17th December 1997
__

Detlef Sieling#### On the Existence of Polynomial Time Approximation Schemes for OBDD Minimization

Revisions: 1

__
TR95-002
| 1st January 1995
__

Detlef Sieling#### New Lower Bounds and Hierarchy Results for Restricted Branching Programs

__
TR94-026
| 12th December 1994
__

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener#### On the Power of Different Types of Restricted Branching Programs

Detlef Sieling

Decision trees are representations of discrete functions with widespread applications in, e.g., complexity theory and data mining and exploration. In these areas it is important to obtain decision trees of small size. The minimization problem for decision trees is known to be NP-hard. In this paper the problem is shown ... more >>>

Petr Savicky, Detlef Sieling

Restricted branching programs are considered in complexity theory in

order to study the space complexity of sequential computations and

in applications as a data structure for Boolean functions. In this

paper (\oplus,k)-branching programs and (\vee,k)-branching

programs are considered, i.e., branching programs starting with a

...
more >>>

Detlef Sieling

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

Detlef Sieling

Free Binary Decision Diagrams (FBDDs) are a data structure

for the representation and manipulation of Boolean functions.

Efficient algorithms for most of the important operations are known if

only FBDDs respecting a fixed graph ordering are considered. However,

the size of such an FBDD may strongly depend on the chosen ...
more >>>

Detlef Sieling

For (1,+k)-branching programs and read-k-times branching

programs syntactic and nonsyntactic variants can be distinguished. The

nonsyntactic variants correspond in a natural way to sequential

computations with restrictions on reading the input while lower bound

proofs are easier or only known for the syntactic variants. In this

paper it is shown ...
more >>>

Detlef Sieling

The size of Ordered Binary Decision Diagrams (OBDDs) is

determined by the chosen variable ordering. A poor choice may cause an

OBDD to be too large to fit into the available memory. The decision

variant of the variable ordering problem is known to be

NP-complete. We strengthen this result by ...
more >>>

Detlef Sieling

In unrestricted branching programs all variables may be tested

arbitrarily often on each path. But exponential lower bounds are only

known, if on each path the number of tests of each variable is bounded

(Borodin, Razborov and Smolensky (1993)). We examine branching programs

in which for each path the ...
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 >>>