The succinct representation of a binary word w is a Boolean circuit that on input of a number i (in binary), outputs whether i [is less than or equal to] |w| and in that case, the ith bit of w (|w| denotes the length of w).
We next describe disjunctive Datalog programs for deciding co-CERT3COL and for simulating a Boolean circuit. The programs are used in the proof of Theorem 8.8.
Lemma 8.7 For any Boolean circuit C, [M.sub.C] is the unique minimal model of ground ([[Pi].sub.C], [U.sub.0]).
Let [C.sub.I] be the Boolean circuit of an instance I of co-CERT3COL of size n.
Without loss of generality, we could bypass or-gates in the Boolean circuit simulation, by simulating or-gates with and-gates and not-gates.
For every Boolean circuit C, there exists an equivalent Boolean circuit C' that has O(|C|) size, so that C' has negation only immediately after input gates; moreover, such a C' can be easily constructed from C in logspace.