
| L       | NNF   | DNNF   | d-DNNF   | sd-DNNF   | FBDD   | OBDD   | OBDD<   | DNF   | CNF   | PI   | IP   | MODS   |
|---------|-------|--------|----------|-----------|--------|--------|---------|-------|-------|------|------|--------|
| NNF     | ≤     | ≤      | ≤        | ≤         | ≤      | ≤      | ≤       | ≤     | ≤     | ≤    | ≤    | ≤      |
| DNNF    | 6≤ ∗  | ≤      | ≤        | ≤         | ≤      | ≤      | ≤       | ≤     | 6≤ ∗  | ?    | ≤    | ≤      |
| d-DNNF  | 6≤ ∗  | ∗      | ≤        | ≤         | ≤      | ≤      | ≤       | 6≤ ∗  | ∗     |      |      |        |
| 6≤      | 6≤    | ?      | ?        | ≤         |        |        |         |       |       |      |      |        |
| ∗       | ∗     | ≤      | ≤        | ≤         | ≤      | ≤      | 6≤ ∗    | ∗     |       |      |      |        |
| sd-DNNF | 6≤    |        | ?        | ?         | ≤      |        |         |       |       |      |      |        |
| 6≤      | 6≤    |        |          |           |        |        |         |       |       |      |      |        |
| FBDD    | 6≤    | 6≤     | 6≤       | 6≤        | ≤      | ≤      | ≤       | 6≤    | 6≤    | 6≤   | 6≤   | ≤      |
| OBDD    | 6≤    | 6≤     | 6≤       | 6≤        | 6≤     | ≤      | ≤       | 6≤    | 6≤    | 6≤   | 6≤   | ≤      |
| OBDD<   | 6≤    | 6≤     | 6≤       | 6≤        | 6≤     | 6≤     | ≤       | 6≤    | 6≤    | 6≤   | 6≤   | ≤      |
| DNF     | 6≤    | 6≤     | 6≤       | 6≤        | 6≤     | 6≤     | 6≤      | ≤     | 6≤    | 6≤   | ≤    | ≤      |
| CNF     | 6≤    | 6≤     | 6≤       | 6≤        | 6≤     | 6≤     | 6≤      | 6≤    | ≤     | ≤    | 6≤   | ≤      |
| PI      | 6≤    | 6≤     | 6≤       | 6≤        | 6≤     | 6≤     | 6≤      | 6≤    | 6≤    | ≤    | 6≤   | ?      |
| IP      | 6≤    | 6≤     | 6≤       | 6≤        | 6≤     | 6≤     | 6≤      | 6≤    | 6≤    | 6≤   | ≤    | ≤      |
| MODS    | 6≤    | 6≤     | 6≤       | 6≤        | 6≤     | 6≤     | 6≤      | 6≤    | 6≤    | 6≤   | 6≤   | ≤      |

Table 3: Succinctness of target compilation languages. ∗ **means that the result holds unless the**
polynomial hierarchy collapses.

![0_image_0.png](0_image_0.png)

Figure 5: An edge L1 → L2 indicates that L1 is strictly more succinct than L2: L1 < L2**, while**
L1 = L2 indicates that L1 and L2 are equally succinct: L1 ≤ L2 and L2 ≤ L1**. Dotted**
arrows indicate unknown relationships; for instance, the dotted arrow from DNNF to PI means that we do not know whether DNNF is at least as succinct as PI**. Some of the edges**
are conditioned on the polynomial hierarchy not collapsing—see Table 3.

sd-DNNF **(which is more succinct than the influential** FBDD, OBDD and OBDD< **languages) with** MODS,
which is a most tractable language. Both sd-DNNF and MODS **are smooth, deterministic and decomposable.** MODS**, however, is flat and obtains its decomposability from the stronger condition**
of simple-conjunction. Therefore, sd-DNNF **can be viewed as the result of relaxing from** MODS the flatness and simple-conjunction conditions, while maintaining decomposability, determinism and smoothness. Relaxing these conditions moves the language three levels up the succinctness hierarchy, although it compromises only the polytime test for sentential entailment and possibly the one for equivalence as we show in Section 4.