In this paper we study the role of cliquewidth in succinct representation of
Boolean functions. Our main statement is the following: Let $Z$ be a Boolean
circuit having cliquewidth $k$. Then there is another circuit $Z^*$ computing
the same function as $Z$ having treewidth at most $18k+2$ and which has at most
$4|Z|$ gates where $|Z|$ is the number of gates of $Z$. In this sense,
cliquewidth is not more `powerful' than treewidth for the purpose of
representation of Boolean functions. We believe this is quite a surprising fact
because it contrasts the situation with graphs where an upper bound on the
treewidth implies an upper bound on the cliquewidth but not vice versa.
We demonstrate the usefulness of the new theorem for knowledge compilation.
In particular, we show that a circuit $Z$ of cliquewidth $k$ can be compiled
into a Decomposable Negation Normal Form ({\sc dnnf}) of size
$O(9^{18k}k^2|Z|)$ and the same runtime. To the best of our knowledge, this is
the first result on efficient knowledge compilation parameterized by
cliquewidth of a Boolean circuit.

本文研究了丛图宽度在布尔函数简洁表示中的作用，并推出了相应结论。该结论表明，丛图宽度对于表示布尔函数并不比树宽更加 “强大”，并且演示了该结论在知识编译中的应用。同时提出了一种可行的算法，能够将丛图宽度小于等于 k 的布尔电路编译成大小为 $O (9^{18k} k^2|Z|)$，执行时间也相同的分解否定标准式 (DNNF)。

团宽和知识编译

Cliquewidth and Knowledge Compilation

We introduced decomposable negation normal form (DNNF) recently as a
tractable form of propositional theories, and provided a number of powerful
logical operations that can be performed on it in polynomial time. We also
presented an algorithm for compiling any conjunctive normal form (CNF) into
DNNF and provided a structure-based guarantee on its space and time complexity.
We present in this paper a linear-time algorithm for converting an ordered
binary decision diagram (OBDD) representation of a propositional theory into an
equivalent DNNF, showing that DNNFs scale as well as OBDDs. We also identify a
subclass of DNNF which we call deterministic DNNF, d-DNNF, and show that the
previous complexity guarantees on compiling DNNF continue to hold for this
stricter subclass, which has stronger properties. In particular, we present a
new operation on d-DNNF which allows us to count its models under the
assertion, retraction and flipping of every literal by traversing the d-DNNF
twice. That is, after such traversal, we can test in constant-time: the
entailment of any literal by the d-DNNF, and the consistency of the d-DNNF
under the retraction or flipping of any literal. We demonstrate the
significance of these new operations by showing how they allow us to implement
linear-time, complete truth maintenance systems and linear-time, complete
belief revision systems for two important classes of propositional theories.

本文介绍了可分解否定范式（DNNF）作为可行的命题理论形式，并提供了一些在多项式时间内可以执行的强大逻辑操作。在此基础上，本文提出了将任何合取范式（CNF）转化为 DNNF 的算法，并提供其空间和时间复杂度上的结构保证。同时它也介绍了将有序二叉决策图（OBDD）表示的命题理论转换为等价的 DNNF 的线性时间算法。接着，介绍了采用新的操作在 d-DNNF 上遍历之后实现线性时间、完整的信念修正系统。