Reducibility concepts are fundamental in complexity theory.
Usually, they are defined as follows: A problem P is reducible
to a problem S if P can be computed using a program or device
for S as a subroutine. However, this approach has its limitations
if restricted computational models are considered. In the case
of ordered binary decision diagrams (OBDDs), it allows merely
to use the almost unmodified original program for the subroutine.

Here we propose a new reducibility concept for OBDDs:
We say that P is reducible to S if an OBDD for P can be
constructed by applying a sequence of elementary operations
to an OBDD for S. In contrast to traditional reducibility
notions, the newly introduced reduction is able to reflect
the real needs of a reducibility concept in the context of
OBDD-based complexity classes: it allows to reduce those
problems to each other which are computable with the same
amount of OBDD-resources and it gives a tool to carry over
lower and upper bounds.

Reducibility concepts are fundamental in complexity theory.
Usually, they are defined as follows: A problem P is reducible
to a problem S if P can be computed using a program or device
for S as a subroutine. However, in the case of such restricted
models as ordered binary decision diagrams (OBDDs), this ap-
proach is very limited in its power and leads necessarily to
concepts which are quite meaningless for complexity theoretic
considerations.
In the paper, we propose a new reducibility concept for
OBDDs. We say that P is reducible to S if an OBDD for P can be
constructed by applying a sequence of computationally elemen-
tary operations to an OBDD for S instead of using the unmodi-
fied OBDD for S as a subroutine. Hence, P is reducible to S
means that it is somewhat clear how to obtain a program for P
from a program for S without insisting on an almost unmodified
use of the original program.
Although well-motivated, defining reducibility in terms of
sequences of elementary operations has the disadvantage that
it is very difficult to handle dynamically changing struc-
tures. The main purpose of this paper is to establish an algo-
rithmically based static description of this dynamical reduci-
bility notion which makes adequate complexity theoretic inves-
tigations possible.