
Ordered Binary Decision Diagrams (OBDDs) are a data structure that is used in
an increasing number of fields of Computer Science (e.g., logic synthesis,
program verification, data mining, bioinformatics, and data protection) for
representing and manipulating discrete structures and Boolean functions. The
purpose of this paper is to study the error resilience of OBDDs and to design a
resilient version of this data structure, i.e., a selfrepairing OBDD. In
particular, we describe some strategies that make reduced ordered OBDDs
resilient to errors in the indexes, that are associated to the input variables,
or in the pointers (i.e., OBDD edges) of the nodes. These strategies exploit
the inherent redundancy of the data structure, as well as the redundancy
introduced by its efficient implementations. The solutions we propose allow the
exact restoring of the original OBDD and are suitable to be applied to
classical software packages for the manipulation of OBDDs currently in use.
Another result of the paper is the definition of a new canonical OBDD model,
called {\em Indexresilient Reduced OBDD}, which guarantees that a node with a
faulty index has a reconstruction cost $O(k)$, where $k$ is the number of nodes
with corrupted index.

Given a Boolean function f on n variables, a Disjoint SumofProducts (DSOP)
of f is a set of products (ANDs) of subsets of literals whose sum (OR) equals
f, such that no two products cover the same minterm of f. DSOP forms are a
special instance of partial DSOPs, i.e. the general case where a subset of
minterms must be covered exactly once and the other minterms (typically
corresponding to don't care conditions of $f$) can be covered any number of
times. We discuss finding DSOPs and partial DSOP with a minimal number of
products, a problem theoretically connected with various properties of Boolean
functions and practically relevant in the synthesis of digital circuits.
Finding an absolute minimum is hard, in fact we prove that the problem of
absolute minimization of partial DSOPs is NPhard. Therefore it is crucial to
devise a polynomial time heuristic that compares favorably with the known
minimization tools. To this end we develop a further piece of theory starting
from the definition of the weight of a product p as a functions of the number
of fragments induced on other cubes by the selection of p, and show how product
weights can be exploited for building a class of minimization heuristics for
DSOP and partial DSOP synthesis. A set of experiments conducted on major
benchmark functions show that our method, with a family of variants, always
generates better results than the ones of previous heuristics, including the
method based on a BDD representation of f.

Cubelike graphs are the Cayley graphs of the elementary abelian group (Z_2)^n
(e.g., the hypercube is a cubelike graph). We give conditions for perfect state
transfer between two particles in quantum networks modeled by a large class of
cubelike graphs. This generalizes results of Christandl et al. [Phys. Rev.
Lett. 92, 187902 (2004)] and Facer et al. [Phys. Rev. A 92, 187902 (2008)].