Please report any queries concerning the funding data grouped in the sections named "Externally Awarded" or "Internally Disbursed" (shown on the profile page) to
your Research Finance Administrator. Your can find your Research Finance Administrator at https://www.ucl.ac.uk/finance/research/rs-contacts.php by entering your department
Please report any queries concerning the student data shown on the profile page to:
Email: portico-services@ucl.ac.uk
Help Desk: http://www.ucl.ac.uk/ras/portico/helpdesk
Email: portico-services@ucl.ac.uk
Help Desk: http://www.ucl.ac.uk/ras/portico/helpdesk
Publication Detail
Cliquewidth and Knowledge Compilation
-
Publication Type:Conference
-
Authors:Razgon I, Petke J
-
Keywords:cs.LO, cs.LO
-
Author URL:
Abstract
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.
› More search options
UCL Researchers