Bibliography

46 results

• [bib] 2018
  Antoine Amarilli, Florent Capelli, Mikaël Monet, and Pierre Senellart, "Connecting Knowledge Compilation Classes and Width Parameters," CoRR, vol. abs/1811.02944, 2018. Amarilli_2018

  cSDD : ∧BCcSDD : ∧CcSDD : ∨BCcSDD : ∨CcSDD$_T$ : ∧CcSDD$_T$ : ∨CcSDD$_T$ : FOd-SDNNF : ∧BCd-SDNNF : ∧Cd-SDNNF : ∨BCd-SDNNF : ∨Cd-SDNNF$_T$ : ∧Cd-SDNNF$_T$ : ∨Cdec-DNNF : ∧BCdec-DNNF : ∧Cdec-DNNF : ∨BCdec-DNNF : ∨Cdec-SDNNF : ∧BCdec-SDNNF : ∧Cdec-SDNNF : ∨BCdec-SDNNF : ∨Cdec-SDNNF$_T$ : ∧Cdec-SDNNF$_T$ : ∨CnFBDD : ¬CnFBDD : ∧BCnFBDD : ∧CnOBDD : ¬CnOBDD : ∧BCnOBDD : ∧CnOBDD : ∨BCnOBDD$_<$ : ¬CnOBDD$_<$ : ∧COBDD : ∨BCSDD : ∧BCSDD : ∧CSDD : ∨BCSDD$_T$ : ∧CSDD$_T$ : ∨CSDD$_T$ : FOSDNNF : ¬CSDNNF : ∧BCSDNNF : ∧CSDNNF : ∨BCSDNNF$_T$ : ¬CSDNNF$_T$ : ∧CTDD : ∧BCTDD : ∧CTDD : ∨BCTDD : ∨CTDD : FOTDD$_T$ : ∧CTDD$_T$ : ∨CTDD$_T$ : FOuFBDD : ∧BCuFBDD : ∧CuFBDD : ∨BCuOBDD : ∧BCuOBDD : ∧CuOBDD : ∨BCuOBDD : ∨CuOBDD$_<$ : ∧CuOBDD$_<$ : ∨Cd-SDNNF -> d-DNNFd-SDNNF -> SDNNFd-SDNNF -> uOBDDd-SDNNF$_T$ -> nFBDDd-SDNNF$_T$ -> SDNNF$_T$d-SDNNF$_T$ -> uOBDD$_<$dec-DNNF -> d-DNNFdec-DNNF -> FBDDdec-SDNNF -> d-SDNNFdec-SDNNF -> dec-DNNFdec-SDNNF -> OBDDdec-SDNNF$_T$ -> d-SDNNF$_T$dec-SDNNF$_T$ -> dec-SDNNFdec-SDNNF$_T$ -> nFBDDdec-SDNNF$_T$ -> OBDD$_<$DNF -> d-SDNNFDNF -> nOBDD$_<$DNNF -> nFBDDFBDD -> dec-DNNFFBDD -> uFBDDnFBDD -> d-DNNFnFBDD -> DNNFnFBDD -> FBDDnFBDD -> uFBDDnOBDD -> nFBDDnOBDD -> SDNNFnOBDD$_<$ -> SDNNF$_T$OBDD -> dec-SDNNFOBDD -> uOBDDOBDD$_<$ -> dec-SDNNF$_T$OBDD$_<$ -> uOBDD$_<$SDNNF -> DNNFSDNNF -> nOBDDSDNNF$_T$ -> nOBDD$_<$uFBDD -> d-DNNFuFBDD -> FBDDuFBDD -> nFBDDuOBDD -> d-SDNNFuOBDD -> nOBDDuOBDD -> uFBDDuOBDD$_<$ -> d-SDNNF$_T$uOBDD$_<$ -> nOBDD$_<$

  cSDD : ∧BCcSDD : ∧CcSDD : ∨BCcSDD : ∨CcSDD$_T$ : ∧CcSDD$_T$ : ∨CcSDD$_T$ : FOd-SDNNF : ∧BCd-SDNNF : ∧Cd-SDNNF : ∨BCd-SDNNF : ∨Cd-SDNNF$_T$ : ∧Cd-SDNNF$_T$ : ∨Cdec-DNNF : ∧BCdec-DNNF : ∧Cdec-DNNF : ∨BCdec-DNNF : ∨Cdec-SDNNF : ∧BCdec-SDNNF : ∧Cdec-SDNNF : ∨BCdec-SDNNF : ∨Cdec-SDNNF$_T$ : ∧Cdec-SDNNF$_T$ : ∨CnFBDD : ¬CnFBDD : ∧BCnFBDD : ∧CnOBDD : ¬CnOBDD : ∧BCnOBDD : ∧CnOBDD : ∨BCnOBDD$_<$ : ¬CnOBDD$_<$ : ∧COBDD : ∨BCSDD : ∧BCSDD : ∧CSDD : ∨BCSDD$_T$ : ∧CSDD$_T$ : ∨CSDD$_T$ : FOSDNNF : ¬CSDNNF : ∧BCSDNNF : ∧CSDNNF : ∨BCSDNNF$_T$ : ¬CSDNNF$_T$ : ∧CTDD : ∧BCTDD : ∧CTDD : ∨BCTDD : ∨CTDD : FOTDD$_T$ : ∧CTDD$_T$ : ∨CTDD$_T$ : FOuFBDD : ∧BCuFBDD : ∧CuFBDD : ∨BCuOBDD : ∧BCuOBDD : ∧CuOBDD : ∨BCuOBDD : ∨CuOBDD$_<$ : ∧CuOBDD$_<$ : ∨Cd-SDNNF -> d-DNNFd-SDNNF -> SDNNFd-SDNNF -> uOBDDd-SDNNF$_T$ -> nFBDDd-SDNNF$_T$ -> SDNNF$_T$d-SDNNF$_T$ -> uOBDD$_<$dec-DNNF -> d-DNNFdec-DNNF -> FBDDdec-SDNNF -> d-SDNNFdec-SDNNF -> dec-DNNFdec-SDNNF -> OBDDdec-SDNNF$_T$ -> d-SDNNF$_T$dec-SDNNF$_T$ -> dec-SDNNFdec-SDNNF$_T$ -> nFBDDdec-SDNNF$_T$ -> OBDD$_<$DNF -> d-SDNNFDNF -> nOBDD$_<$DNNF -> nFBDDFBDD -> dec-DNNFFBDD -> uFBDDnFBDD -> d-DNNFnFBDD -> DNNFnFBDD -> FBDDnFBDD -> uFBDDnOBDD -> nFBDDnOBDD -> SDNNFnOBDD$_<$ -> SDNNF$_T$OBDD -> dec-SDNNFOBDD -> uOBDDOBDD$_<$ -> dec-SDNNF$_T$OBDD$_<$ -> uOBDD$_<$SDNNF -> DNNFSDNNF -> nOBDDSDNNF$_T$ -> nOBDD$_<$uFBDD -> d-DNNFuFBDD -> FBDDuFBDD -> nFBDDuOBDD -> d-SDNNFuOBDD -> nOBDDuOBDD -> uFBDDuOBDD$_<$ -> d-SDNNF$_T$uOBDD$_<$ -> nOBDD$_<$ +
  bib
• [bib] 2013
  Paul Beame, Jerry Li, Sudeepa Roy, and Dan Suciu, "Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases," 2013. Beame_2013

  dec-DNNF : ∨Cdec-SDNNF$_T$ : ∧Cd-SDNNF -> uOBDDdec-DNNF -> FBDDdec-SDNNF -> OBDDdec-SDNNF$_T$ -> nFBDDdec-SDNNF$_T$ -> OBDD$_<$DNNF -> nFBDDSDNNF -> nOBDD

  dec-DNNF : ∨Cdec-SDNNF$_T$ : ∧Cd-SDNNF -> uOBDDdec-DNNF -> FBDDdec-SDNNF -> OBDDdec-SDNNF$_T$ -> nFBDDdec-SDNNF$_T$ -> OBDD$_<$DNNF -> nFBDDSDNNF -> nOBDD +
  bib
• [bib] 2015
  Paul Beame and Vincent Liew, "New Limits for Knowledge Compilation and Applications to Exact Model Counting," 2015. Beame_2015

  cSDD$_T$ : ∧Cd-SDNNF$_T$ : ∧CSDD$_T$ : ∧CTDD$_T$ : ∧CuOBDD$_<$ : ∧Cd-SDNNF -> uOBDDd-SDNNF$_T$ -> nFBDDd-SDNNF$_T$ -> uOBDD$_<$dec-SDNNF -> OBDDdec-SDNNF$_T$ -> OBDD$_<$DNNF -> nFBDDFBDD -> SDDSDNNF -> nOBDDSDNNF$_T$ -> nOBDD$_<$

  cSDD$_T$ : ∧Cd-SDNNF$_T$ : ∧CSDD$_T$ : ∧CTDD$_T$ : ∧CuOBDD$_<$ : ∧Cd-SDNNF -> uOBDDd-SDNNF$_T$ -> nFBDDd-SDNNF$_T$ -> uOBDD$_<$dec-SDNNF -> OBDDdec-SDNNF$_T$ -> OBDD$_<$DNNF -> nFBDDFBDD -> SDDSDNNF -> nOBDDSDNNF$_T$ -> nOBDD$_<$ +
  bib
• [bib] 1980
  M. Blum, A. K. Chandra, and M. N. Wegman, "Equivalence of free boolean graphs can be decided probabilistically in polynomial time," Information Processing Letters, vol. 10, pp. 80–82, 1980. Blum_1980

  FBDD : EQ

  FBDD : EQ +
  bib
• [bib] 1993
  H. L. Bodlaender, "A Linear Time Algorithm for Finding Tree-decompositions of Small Treewidth," Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, pp. 226–234, 1993. Bodlaender_1993

  d-SDNNF -> uOBDDDNNF -> nFBDDSDNNF -> nOBDD

  d-SDNNF -> uOBDDDNNF -> nFBDDSDNNF -> nOBDD +
  bib
• [bib] 2018
  Beate Bollig and Matthias Buttkus, "On the Relative Succinctness of Sentential Decision Diagrams," 2018. Bollig_2018

  cSDD$_T$ : ∧Cd-SDNNF$_T$ : ∧CSDD$_T$ : ∧CTDD$_T$ : ∧CuOBDD$_<$ : ∧Cd-SDNNF -> uOBDDd-SDNNF$_T$ -> nFBDDd-SDNNF$_T$ -> uOBDD$_<$dec-SDNNF -> OBDDdec-SDNNF$_T$ -> OBDD$_<$DNNF -> nFBDDSDD$_T$ -> FBDDSDNNF -> nOBDDSDNNF$_T$ -> nOBDD$_<$

  cSDD$_T$ : ∧Cd-SDNNF$_T$ : ∧CSDD$_T$ : ∧CTDD$_T$ : ∧CuOBDD$_<$ : ∧Cd-SDNNF -> uOBDDd-SDNNF$_T$ -> nFBDDd-SDNNF$_T$ -> uOBDD$_<$dec-SDNNF -> OBDDdec-SDNNF$_T$ -> OBDD$_<$DNNF -> nFBDDSDD$_T$ -> FBDDSDNNF -> nOBDDSDNNF$_T$ -> nOBDD$_<$ +
  bib
• [bib] 2014
  S. Bova, F. Capelli, S. Mengel, and F. Slivovsky, "Expander CNFs have exponential DNNF size," 2014. Bova_2014

  cSDD : ∧CcSDD$_T$ : ∧Cd-SDNNF : ∧Cd-SDNNF$_T$ : ∧Cdec-DNNF : ∧Cdec-SDNNF : ∧Cdec-SDNNF$_T$ : ∧CDNF : ¬CDNF : ∧CDNNF : ¬CDNNF : ∧CnFBDD : ¬CnFBDD : ∧CnOBDD : ¬CnOBDD : ∧CnOBDD$_<$ : ¬CnOBDD$_<$ : ∧CSDD : ∧CSDD$_T$ : ∧CSDNNF : ¬CSDNNF : ∧CSDNNF$_T$ : ¬CSDNNF$_T$ : ∧CTDD : ∧CTDD$_T$ : ∧CuFBDD : ∧CuOBDD : ∧CuOBDD$_<$ : ∧CCNF -> DNNFDNNF -> d-DNNF

  cSDD : ∧CcSDD$_T$ : ∧Cd-SDNNF : ∧Cd-SDNNF$_T$ : ∧Cdec-DNNF : ∧Cdec-SDNNF : ∧Cdec-SDNNF$_T$ : ∧CDNF : ¬CDNF : ∧CDNNF : ¬CDNNF : ∧CnFBDD : ¬CnFBDD : ∧CnOBDD : ¬CnOBDD : ∧CnOBDD$_<$ : ¬CnOBDD$_<$ : ∧CSDD : ∧CSDD$_T$ : ∧CSDNNF : ¬CSDNNF : ∧CSDNNF$_T$ : ¬CSDNNF$_T$ : ∧CTDD : ∧CTDD$_T$ : ∧CuFBDD : ∧CuOBDD : ∧CuOBDD$_<$ : ∧CCNF -> DNNFDNNF -> d-DNNF +
  bib
• [bib] 2016
  S. Bova, F. Capelli, S. Mengel, and F. Slivovsky, "Knowledge Compilation Meets Communication Complexity," 25th International Joint Conference on Artificial Intelligence (IJCAI'16), pp. 1008–1014, 2016. Bova_2016

  d-DNNF : ∨BCdec-DNNF : ∨BCFBDD : ∨BCuFBDD : ∨BCDNNF -> d-DNNFPI -> DNNFuFBDD -> FBDD

  d-DNNF : ∨BCdec-DNNF : ∨BCFBDD : ∨BCuFBDD : ∨BCDNNF -> d-DNNFPI -> DNNFuFBDD -> FBDD +
  bib
• [bib] 2016
  S. Bova, "SDDs Are Exponentially More Succinct than OBDDs," Proceedings of the AAAI Conference on Artificial Intelligence, vol. 30, 2016. Bova_2016_a

  cSDD -> OBDDcSDD$_T$ -> OBDDcSDD$_T$ -> OBDD$_<$

  cSDD -> OBDDcSDD$_T$ -> OBDDcSDD$_T$ -> OBDD$_<$ +
  bib
• [bib] 1986
  R. E. Bryant, "Graph-based algorithms for boolean function manipulation," IEEE Transactions on Computers, vol. C-35, pp. 677–691, 1986. Bryant_1986

  OBDD : CTOBDD$_<$ : COOBDD$_<$ : CTOBDD$_<$ : EQOBDD$_<$ : MEOBDD$_<$ : VAOBDD$_<$ : ¬COBDD$_<$ : ∧BCOBDD$_<$ : ∨BCOBDD$_<$ : CDcSDD$_T$ -> OBDD$_<$FBDD -> OBDDuOBDD -> OBDD

  OBDD : CTOBDD$_<$ : COOBDD$_<$ : CTOBDD$_<$ : EQOBDD$_<$ : MEOBDD$_<$ : VAOBDD$_<$ : ¬COBDD$_<$ : ∧BCOBDD$_<$ : ∨BCOBDD$_<$ : CDcSDD$_T$ -> OBDD$_<$FBDD -> OBDDuOBDD -> OBDD +
  bib
• [bib] 1992
  R. E. Bryant, "Symbolic Boolean manipulation with ordered binary-decision diagrams," ACM Computing Surveys, vol. 24, pp. 293–318, 1992. Bryant_1992

  FBDD : COFBDD : CTFBDD : VAOBDD$_<$ : CTOBDD$_<$ : EQ

  FBDD : COFBDD : CTFBDD : VAOBDD$_<$ : CTOBDD$_<$ : EQ +
  bib
• [bib] 2016
  Florent Capelli, "Structural Restrictions of CNF-formulas: Applications to Model Counting and Knowledge Compilation," 2016. Capelli_2016

  FBDD -> SDNNF

  FBDD -> SDNNF +
  bib
• [bib] 2026
  F. Capelli, Y. Choi, S. Mengel, M. Muñoz, and G. Van den Broeck, "A canonical generalization of OBDD," 2026. Capelli_2026

  TDD : ¬CTDD : ∧BCTDD : ∧CTDD : ∨BCTDD : ∨CTDD : CDTDD : FOTDD : SFOTDD$_T$ : ¬CTDD$_T$ : ∧BCTDD$_T$ : ∧CTDD$_T$ : ∨CTDD$_T$ : CDTDD$_T$ : FOOBDD -> TDDOBDD$_<$ -> TDD$_T$TDD -> d-SDNNFTDD -> SDDTDD$_T$ -> d-SDNNF$_T$TDD$_T$ -> OBDDTDD$_T$ -> SDD$_T$TDD$_T$ -> TDD

  TDD : ¬CTDD : ∧BCTDD : ∧CTDD : ∨BCTDD : ∨CTDD : CDTDD : FOTDD : SFOTDD$_T$ : ¬CTDD$_T$ : ∧BCTDD$_T$ : ∧CTDD$_T$ : ∨CTDD$_T$ : CDTDD$_T$ : FOOBDD -> TDDOBDD$_<$ -> TDD$_T$TDD -> d-SDNNFTDD -> SDDTDD$_T$ -> d-SDNNF$_T$TDD$_T$ -> OBDDTDD$_T$ -> SDD$_T$TDD$_T$ -> TDD +
  bib
• [bib] 1978
  A. K. Chandra and G. Markowsky, "On the Number of Prime Implicants," Discrete Mathematics, vol. 24, pp. 7–11, 1978. Chandra_1978

  IP : ∨BCIP : SFOPI : ∧BC

  IP : ∨BCIP : SFOPI : ∧BC +
  bib
• [bib] 1971
  S. A. Cook, "The Complexity of Theorem-Proving Procedures," Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151–158, 1971. Cook_1971

  CNF : CO

  CNF : CO +
  bib
• [bib] 2000
  Adnan Darwiche, "On the tractable counting of theory models and its application to belief revision and truth maintenance," 2000. Darwiche_2000

  d-DNNF -> FBDD

  d-DNNF -> FBDD +
  bib
• [bib] 2001
  A. Darwiche, "Decomposable Negation Normal Form," Journal of the ACM, vol. 48, pp. 608–647, 2001. Darwiche_2001a

  DNNF : COcSDD : ∧BCcSDD : ∧Cd-DNNF : ∧BCd-SDNNF : ∧BCd-SDNNF : ∧Cdec-DNNF : ∧BCdec-DNNF : ∧Cdec-SDNNF : ∧BCdec-SDNNF : ∧CDNNF : ∧BCDNNF : FOFBDD : ∧BCMODS : FOOBDD : ∧BCSDD : ∧BCSDD : ∧CTDD : ∧BCTDD : ∧CuFBDD : ∧BCuFBDD : ∧CuOBDD : ∧BCuOBDD : ∧Cd-DNNF -> DNNFd-SDNNF -> uOBDDDNNF -> nFBDDSDNNF -> nOBDD

  DNNF : COcSDD : ∧BCcSDD : ∧Cd-DNNF : ∧BCd-SDNNF : ∧BCd-SDNNF : ∧Cdec-DNNF : ∧BCdec-DNNF : ∧Cdec-SDNNF : ∧BCdec-SDNNF : ∧CDNNF : ∧BCDNNF : FOFBDD : ∧BCMODS : FOOBDD : ∧BCSDD : ∧BCSDD : ∧CTDD : ∧BCTDD : ∧CuFBDD : ∧BCuFBDD : ∧CuOBDD : ∧BCuOBDD : ∧Cd-DNNF -> DNNFd-SDNNF -> uOBDDDNNF -> nFBDDSDNNF -> nOBDD +
  bib
• [bib] 2001
  A. Darwiche, "On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision," Journal of Applied Non-Classical Logics, vol. 11, pp. 11–34, 2001. Darwiche_2001b

  d-DNNF : CT

  d-DNNF : CT +
  bib
• [bib] 2002
  A. Darwiche and P. Marquis, "A Knowledge Compilation Map," Journal of Artificial Intelligence Research, vol. 17, pp. 229–264, 2002. Darwiche_2002

  CNF : IMCNF : VAd-DNNF : CTDNF : VADNNF : COIP : CTIP : IMIP : SEMODS : COMODS : CTOBDD : CTOBDD : EQOBDD : SEPI : CEPI : CTPI : SECNF : ∧CCNF : ∨BCCNF : ∨CCNF : CDCNF : FOcSDD : ∧BCcSDD : ∧CcSDD : ∨CcSDD$_T$ : ∧CcSDD$_T$ : ∨CcSDD$_T$ : FOd-DNNF : ∧BCd-DNNF : ∨BCd-DNNF : CDd-SDNNF : ∧BCd-SDNNF : ∧Cd-SDNNF : ∨Cd-SDNNF$_T$ : ∧Cd-SDNNF$_T$ : ∨Cdec-DNNF : ∧BCdec-DNNF : ∧Cdec-DNNF : ∨BCdec-DNNF : ∨Cdec-SDNNF : ∧BCdec-SDNNF : ∧Cdec-SDNNF : ∨Cdec-SDNNF$_T$ : ∧Cdec-SDNNF$_T$ : ∨CDNF : ¬CDNF : ∧BCDNF : ∧CDNF : ∨CDNF : FODNNF : ¬CDNNF : ∧BCDNNF : ∧CDNNF : ∨CDNNF : CDDNNF : FOFBDD : ¬CFBDD : ∧BCFBDD : ∧CFBDD : ∨BCFBDD : ∨CFBDD : CDIP : ¬CIP : ∧BCIP : ∧CIP : ∨BCIP : CDIP : SFOMODS : ¬CMODS : ∧BCMODS : ∧CMODS : ∨BCMODS : FOnFBDD : ∧BCnFBDD : ∧CNNF : ¬CNNF : ∧CNNF : CDNNF : FOnOBDD : ∧CnOBDD$_<$ : ∧COBDD : ¬COBDD : ∧BCOBDD : ∧COBDD : ∨COBDD : CDOBDD : FOOBDD : SFOOBDD$_<$ : ∨COBDD$_<$ : FOPI : ¬CPI : ∧BCPI : ∨BCPI : ∨CPI : CDPI : FOSDD : ∧BCSDD : ∧CSDD$_T$ : ∧CSDD$_T$ : ∨CSDD$_T$ : FOSDNNF : ∧CSDNNF$_T$ : ∧CTDD : ∧BCTDD : ∧CTDD : ∨CTDD : FOTDD$_T$ : ∧CTDD$_T$ : ∨CTDD$_T$ : FOuFBDD : ∧BCuFBDD : ∧CuFBDD : ∨BCuOBDD : ∧BCuOBDD : ∧CuOBDD : ∨CuOBDD$_<$ : ∧CuOBDD$_<$ : ∨CCNF -> NNFCNF -> PId-DNNF -> DNNFd-DNNF -> MODSd-SDNNF -> uOBDDdec-SDNNF -> OBDDdec-SDNNF$_T$ -> OBDD$_<$DNF -> d-DNNFDNF -> DNNFDNF -> IPDNNF -> nFBDDDNNF -> NNFFBDD -> d-DNNFIP -> CNFIP -> DNFIP -> FBDDIP -> MODSMODS -> CNFMODS -> d-DNNFMODS -> DNFMODS -> OBDD$_<$OBDD -> FBDDOBDD$_<$ -> CNFOBDD$_<$ -> DNFOBDD$_<$ -> OBDDPI -> CNFPI -> DNFPI -> FBDDPI -> MODSSDNNF -> nOBDD

  CNF : IMCNF : VAd-DNNF : CTDNF : VADNNF : COIP : CTIP : IMIP : SEMODS : COMODS : CTOBDD : CTOBDD : EQOBDD : SEPI : CEPI : CTPI : SECNF : ∧CCNF : ∨BCCNF : ∨CCNF : CDCNF : FOcSDD : ∧BCcSDD : ∧CcSDD : ∨CcSDD$_T$ : ∧CcSDD$_T$ : ∨CcSDD$_T$ : FOd-DNNF : ∧BCd-DNNF : ∨BCd-DNNF : CDd-SDNNF : ∧BCd-SDNNF : ∧Cd-SDNNF : ∨Cd-SDNNF$_T$ : ∧Cd-SDNNF$_T$ : ∨Cdec-DNNF : ∧BCdec-DNNF : ∧Cdec-DNNF : ∨BCdec-DNNF : ∨Cdec-SDNNF : ∧BCdec-SDNNF : ∧Cdec-SDNNF : ∨Cdec-SDNNF$_T$ : ∧Cdec-SDNNF$_T$ : ∨CDNF : ¬CDNF : ∧BCDNF : ∧CDNF : ∨CDNF : FODNNF : ¬CDNNF : ∧BCDNNF : ∧CDNNF : ∨CDNNF : CDDNNF : FOFBDD : ¬CFBDD : ∧BCFBDD : ∧CFBDD : ∨BCFBDD : ∨CFBDD : CDIP : ¬CIP : ∧BCIP : ∧CIP : ∨BCIP : CDIP : SFOMODS : ¬CMODS : ∧BCMODS : ∧CMODS : ∨BCMODS : FOnFBDD : ∧BCnFBDD : ∧CNNF : ¬CNNF : ∧CNNF : CDNNF : FOnOBDD : ∧CnOBDD$_<$ : ∧COBDD : ¬COBDD : ∧BCOBDD : ∧COBDD : ∨COBDD : CDOBDD : FOOBDD : SFOOBDD$_<$ : ∨COBDD$_<$ : FOPI : ¬CPI : ∧BCPI : ∨BCPI : ∨CPI : CDPI : FOSDD : ∧BCSDD : ∧CSDD$_T$ : ∧CSDD$_T$ : ∨CSDD$_T$ : FOSDNNF : ∧CSDNNF$_T$ : ∧CTDD : ∧BCTDD : ∧CTDD : ∨CTDD : FOTDD$_T$ : ∧CTDD$_T$ : ∨CTDD$_T$ : FOuFBDD : ∧BCuFBDD : ∧CuFBDD : ∨BCuOBDD : ∧BCuOBDD : ∧CuOBDD : ∨CuOBDD$_<$ : ∧CuOBDD$_<$ : ∨CCNF -> NNFCNF -> PId-DNNF -> DNNFd-DNNF -> MODSd-SDNNF -> uOBDDdec-SDNNF -> OBDDdec-SDNNF$_T$ -> OBDD$_<$DNF -> d-DNNFDNF -> DNNFDNF -> IPDNNF -> nFBDDDNNF -> NNFFBDD -> d-DNNFIP -> CNFIP -> DNFIP -> FBDDIP -> MODSMODS -> CNFMODS -> d-DNNFMODS -> DNFMODS -> OBDD$_<$OBDD -> FBDDOBDD$_<$ -> CNFOBDD$_<$ -> DNFOBDD$_<$ -> OBDDPI -> CNFPI -> DNFPI -> FBDDPI -> MODSSDNNF -> nOBDD +
  bib
• [bib] 2011
  A. Darwiche, "SDD: a new canonical representation of propositional knowledge bases," Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Two, pp. 819–826, 2011. Darwiche_2011

  cSDD : ∧BCcSDD : ∨BCcSDD$_T$ : ∨CcSDD$_T$ : FOSDD : ¬CSDD : ∧BCSDD : ∨BCSDD : CDSDD$_T$ : ¬CSDD$_T$ : ∧BCSDD$_T$ : ∨BCSDD$_T$ : CDcSDD$_T$ -> cSDDOBDD -> cSDDOBDD$_<$ -> cSDD$_T$SDD$_T$ -> SDD

  cSDD : ∧BCcSDD : ∨BCcSDD$_T$ : ∨CcSDD$_T$ : FOSDD : ¬CSDD : ∧BCSDD : ∨BCSDD : CDSDD$_T$ : ¬CSDD$_T$ : ∧BCSDD$_T$ : ∨BCSDD$_T$ : CDcSDD$_T$ -> cSDDOBDD -> cSDDOBDD$_<$ -> cSDD$_T$SDD$_T$ -> SDD +
  bib
• [bib] 2002
  A. Darwiche and J. Huang, "Testing equivalence probabilistically," 2002. Darwiche_Huang_2002

  d-DNNF : EQ

  d-DNNF : EQ +
  bib
• [bib] 2007
  J. Huang and A. Darwiche, "The Language of Search," Journal of Artificial Intelligence Research, vol. 29, pp. 191–219, 2007. darwiche2007language
  bib
• [bib] 1993
  S. Devadas, "Comparing two-level and ordered binary decision diagram representations of logic functions," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, pp. 722–723, 1993. Devadas_1993

  OBDD : ∨COBDD : FOOBDD$_<$ : ∨COBDD$_<$ : FODNF -> OBDD

  OBDD : ∨COBDD : FOOBDD$_<$ : ∨COBDD$_<$ : FODNF -> OBDD +
  bib
• [bib] 2013
  H. Fargier, P. Marquis, and A. Niveau, "Towards a knowledge compilation map for heterogeneous representation languages," Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, pp. 877–883, 2013. Fargier_2013
  bib
• [bib] 1978
  S. Fortune, J. E. Hopcroft, and E. M. Schmidt, "The Complexity of Equivalence and Containment for Free Single Variable Program Schemes," Automata, Languages and Programming, vol. 62, pp. 227–240, 1978. Fortune_1978

  OBDD : EQ

  OBDD : EQ +
  bib
• [bib] 1994
  J. Gergov and C. Meinel, "Efficient Boolean manipulation with OBDD's can be extended to FBDD's," IEEE Transactions on Computers, vol. 43, pp. 1197–1209, 1994. Gergov_1994

  FBDD : COFBDD : CTFBDD : VAFBDD -> OBDD

  FBDD : COFBDD : CTFBDD : VAFBDD -> OBDD +
  bib
• [bib] 1995
  G. Gogic, H. Kautz, C. H. Papadimitriou, and B. Selman, "The Comparative Linguistics of Knowledge Representation," Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI-95), pp. 862–869, 1995. Gogic_1995
  bib
• [bib] 2002
  S. Jukna and G. Schnitger, "Triangle-Freeness is Hard to Detect," Combinatorics, Probability and Computing, vol. 11, pp. 549–569, 2002. Jukna_2002
  bib
• [bib] 2016
  N. S. Kaleyski, "Boolean methods in knowledge compilation," 2016. Kaleyski_2016

  MODS -> PI

  MODS -> PI +
  bib
• [bib] 2003
  J. Lang, P. Liberatore, and P. Marquis, "Propositional Independence: Formula-Variable Independence and Forgetting," Journal of Artificial Intelligence Research, vol. 18, pp. 391–443, 2003. Lang_2003

  DNF : FO

  DNF : FO +
  bib
• [bib] 1973
  L. A. Levin, "Universal Search Problems," Problems of Information Transmission, vol. 9, pp. 265–266, 1973. Levin_1973

  CNF : CO

  CNF : CO +
  bib
• [bib] 2000
  P. Marquis, "Consequence Finding Algorithms," Handbook of Defeasible Reasoning and Uncertainty Management Systems, vol. 5, pp. 41–145, 2000. Marquis_2000

  IP : ∧BCPI : ∨BCPI : CDPI : FO

  IP : ∧BCPI : ∨BCPI : CDPI : FO +
  bib
• [bib] 1998
  C. Meinel and T. Theobald, "Algorithms and Data Structures in VLSI Design: OBDD - Foundations and Applications," 1998. Meinel_Theobald_1998

  OBDD : EQOBDD : SEOBDD$_<$ : EQ

  OBDD : EQOBDD : SEOBDD$_<$ : EQ +
  bib
• [bib] 2008
  K. Pipatsrisawat and A. Darwiche, "New Compilation Languages Based on Structured Decomposability," Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI-08), pp. 517–522, 2008. Pipatsrisawat_2008

  d-SDNNF : CDd-SDNNF : FOd-SDNNF$_T$ : ∧BCd-SDNNF$_T$ : ∨Cd-SDNNF$_T$ : CDdec-SDNNF$_T$ : ∨CSDD$_T$ : ∨CSDD$_T$ : FOSDNNF : CDSDNNF : FOSDNNF$_T$ : ¬CSDNNF$_T$ : ∧BCSDNNF$_T$ : ∧CSDNNF$_T$ : ∨CSDNNF$_T$ : CDSDNNF$_T$ : FOTDD$_T$ : ∨CTDD$_T$ : FOuOBDD$_<$ : ∨Cd-SDNNF -> uOBDDd-SDNNF$_T$ -> d-SDNNFDNNF -> nFBDDSDNNF -> nOBDDSDNNF$_T$ -> SDNNF

  d-SDNNF : CDd-SDNNF : FOd-SDNNF$_T$ : ∧BCd-SDNNF$_T$ : ∨Cd-SDNNF$_T$ : CDdec-SDNNF$_T$ : ∨CSDD$_T$ : ∨CSDD$_T$ : FOSDNNF : CDSDNNF : FOSDNNF$_T$ : ¬CSDNNF$_T$ : ∧BCSDNNF$_T$ : ∧CSDNNF$_T$ : ∨CSDNNF$_T$ : CDSDNNF$_T$ : FOTDD$_T$ : ∨CTDD$_T$ : FOuOBDD$_<$ : ∨Cd-SDNNF -> uOBDDd-SDNNF$_T$ -> d-SDNNFDNNF -> nFBDDSDNNF -> nOBDDSDNNF$_T$ -> SDNNF +
  bib
• [bib] 2010
  T. Pipatsrisawat, "Reasoning with Propositional Knowledge: Frameworks for Boolean Satisfiability and Knowledge Compilation," 2010. Pipatsrisawat_2010

  FBDD -> SDNNF

  FBDD -> SDNNF +
  bib
• [bib] 1952
  W. V. Quine, "The Problem of Simplifying Truth Functions," The American Mathematical Monthly, vol. 59, pp. 521–531, 1952. Quine_1952
  bib
• [bib] 1996
  D. Roth, "On the Hardness of Approximate Reasoning," Artificial Intelligence, vol. 82, pp. 273–302, 1996. Roth_1996

  PI : CT

  PI : CT +
  bib
• [bib] 2003
  Martin Sauerhoff, "Approximation of boolean functions by combinatorial rectangles," Theoretical Computer Science, vol. 301, pp. 45–78, 2003. Sauerhoff_2003
  bib
• [bib] 1996
  P. Savicky and S. Zak, "A Large Lower Bound for 1-Branching Programs," 1996. Savicky_Zak_1996

  uOBDD -> FBDD

  uOBDD -> FBDD +
  bib
• [bib] 1996
  B. Selman and H. Kautz, "Knowledge compilation and theory approximation," J. ACM, vol. 43, pp. 193–224, 1996. Selman_1996
  bib
• [bib] 2010
  A. Shpilka and A. Yehudayoff, "Arithmetic circuits: A survey of recent results and open questions," Foundations and Trends in Theoretical Computer Science, vol. 5, pp. 207–388, 2010. shpilka2010arithmetic
  bib
• [bib] —
  anonymous, "A Tractable Circuit Zoo," forthcoming. TCZ_Forthcoming

  cSDD : ∧BCcSDD : ∧CcSDD : ∨BCcSDD : ∨CcSDD : SFOcSDD$_T$ : ∧CcSDD$_T$ : ∨CcSDD$_T$ : FOd-DNNF : ∧BCd-DNNF : ∨BCd-DNNF : SFOd-SDNNF : ∧BCd-SDNNF : ∧Cd-SDNNF : ∨BCd-SDNNF : ∨Cd-SDNNF$_T$ : ∧Cd-SDNNF$_T$ : ∨Cd-SDNNF$_T$ : SFOdec-DNNF : ∧BCdec-DNNF : ∧Cdec-DNNF : ∨BCdec-DNNF : ∨Cdec-DNNF : SFOdec-SDNNF : ∧BCdec-SDNNF : ∧Cdec-SDNNF : ∨BCdec-SDNNF : ∨Cdec-SDNNF : SFOdec-SDNNF$_T$ : ∧Cdec-SDNNF$_T$ : ∨Cdec-SDNNF$_T$ : SFODNF : ∧CDNNF : ∧BCDNNF : ∧CFBDD : ∧BCFBDD : ∧CFBDD : ∨BCFBDD : ∨CnFBDD : ∧BCnFBDD : ∧CnFBDD : ∨CnFBDD : FOnOBDD : ∧BCnOBDD : ∧CnOBDD : ∨BCnOBDD : FOnOBDD$_<$ : ∧CnOBDD$_<$ : ∨CnOBDD$_<$ : FOOBDD : ∧BCOBDD : ∧COBDD : ∨BCOBDD : ∨COBDD : FOOBDD$_<$ : ∨COBDD$_<$ : FOSDD : ∧BCSDD : ∧CSDD : ∨BCSDD : SFOSDD$_T$ : ∧CSDD$_T$ : ∨CSDD$_T$ : FOSDNNF : ∧BCSDNNF : ∧CSDNNF : ∨BCSDNNF$_T$ : ∧CTDD : ∧BCTDD : ∧CTDD : ∨BCTDD : ∨CTDD : FOTDD$_T$ : ∧CTDD$_T$ : ∨CTDD$_T$ : FOuFBDD : ∧BCuFBDD : ∧CuFBDD : ∨BCuFBDD : SFOuOBDD : ∧BCuOBDD : ∧CuOBDD : ∨BCuOBDD : ∨CuOBDD$_<$ : ∧CuOBDD$_<$ : ∨CuOBDD$_<$ : SFOd-SDNNF -> uOBDDd-SDNNF$_T$ -> nFBDDd-SDNNF$_T$ -> uOBDD$_<$dec-SDNNF$_T$ -> OBDD$_<$DNNF -> nFBDDOBDD -> SDNNF$_T$SDNNF -> nOBDDSDNNF$_T$ -> nOBDD$_<$

  cSDD : ∧BCcSDD : ∧CcSDD : ∨BCcSDD : ∨CcSDD : SFOcSDD$_T$ : ∧CcSDD$_T$ : ∨CcSDD$_T$ : FOd-DNNF : ∧BCd-DNNF : ∨BCd-DNNF : SFOd-SDNNF : ∧BCd-SDNNF : ∧Cd-SDNNF : ∨BCd-SDNNF : ∨Cd-SDNNF$_T$ : ∧Cd-SDNNF$_T$ : ∨Cd-SDNNF$_T$ : SFOdec-DNNF : ∧BCdec-DNNF : ∧Cdec-DNNF : ∨BCdec-DNNF : ∨Cdec-DNNF : SFOdec-SDNNF : ∧BCdec-SDNNF : ∧Cdec-SDNNF : ∨BCdec-SDNNF : ∨Cdec-SDNNF : SFOdec-SDNNF$_T$ : ∧Cdec-SDNNF$_T$ : ∨Cdec-SDNNF$_T$ : SFODNF : ∧CDNNF : ∧BCDNNF : ∧CFBDD : ∧BCFBDD : ∧CFBDD : ∨BCFBDD : ∨CnFBDD : ∧BCnFBDD : ∧CnFBDD : ∨CnFBDD : FOnOBDD : ∧BCnOBDD : ∧CnOBDD : ∨BCnOBDD : FOnOBDD$_<$ : ∧CnOBDD$_<$ : ∨CnOBDD$_<$ : FOOBDD : ∧BCOBDD : ∧COBDD : ∨BCOBDD : ∨COBDD : FOOBDD$_<$ : ∨COBDD$_<$ : FOSDD : ∧BCSDD : ∧CSDD : ∨BCSDD : SFOSDD$_T$ : ∧CSDD$_T$ : ∨CSDD$_T$ : FOSDNNF : ∧BCSDNNF : ∧CSDNNF : ∨BCSDNNF$_T$ : ∧CTDD : ∧BCTDD : ∧CTDD : ∨BCTDD : ∨CTDD : FOTDD$_T$ : ∧CTDD$_T$ : ∨CTDD$_T$ : FOuFBDD : ∧BCuFBDD : ∧CuFBDD : ∨BCuFBDD : SFOuOBDD : ∧BCuOBDD : ∧CuOBDD : ∨BCuOBDD : ∨CuOBDD$_<$ : ∧CuOBDD$_<$ : ∨CuOBDD$_<$ : SFOd-SDNNF -> uOBDDd-SDNNF$_T$ -> nFBDDd-SDNNF$_T$ -> uOBDD$_<$dec-SDNNF$_T$ -> OBDD$_<$DNNF -> nFBDDOBDD -> SDNNF$_T$SDNNF -> nOBDDSDNNF$_T$ -> nOBDD$_<$ +
  bib
• [bib] 2015
  G. Van den Broeck and A. Darwiche, "On the Role of Canonicity in Knowledge Compilation," Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pp. 1641–1648, 2015. VanDenBroeck_2015

  cSDD : ¬CcSDD : ∧BCcSDD : ∧CcSDD : ∨BCcSDD : ∨CcSDD$_T$ : ¬CcSDD$_T$ : ∧BCcSDD$_T$ : ∧CcSDD$_T$ : ∨CcSDD$_T$ : CDcSDD$_T$ : FOcSDD$_T$ : SFOOBDD : FOOBDD$_<$ : FOSDD : ∧BCSDD : ∧CSDD : ∨BCSDD$_T$ : ∧CSDD$_T$ : ∨CSDD$_T$ : FOTDD : FOTDD$_T$ : FOcSDD -> SDDcSDD$_T$ -> SDD$_T$SDD -> d-SDNNFSDD$_T$ -> cSDD$_T$SDD$_T$ -> d-SDNNF$_T$

  cSDD : ¬CcSDD : ∧BCcSDD : ∧CcSDD : ∨BCcSDD : ∨CcSDD$_T$ : ¬CcSDD$_T$ : ∧BCcSDD$_T$ : ∧CcSDD$_T$ : ∨CcSDD$_T$ : CDcSDD$_T$ : FOcSDD$_T$ : SFOOBDD : FOOBDD$_<$ : FOSDD : ∧BCSDD : ∧CSDD : ∨BCSDD$_T$ : ∧CSDD$_T$ : ∨CSDD$_T$ : FOTDD : FOTDD$_T$ : FOcSDD -> SDDcSDD$_T$ -> SDD$_T$SDD -> d-SDNNFSDD$_T$ -> cSDD$_T$SDD$_T$ -> d-SDNNF$_T$ +
  bib
• [bib] 2024
  H. Vinall-Smeeth, "Structured d-DNNF Is Not Closed Under Negation," Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI-24), pp. 3593–3601, 2024. Vinall-Smeeth_2024

  cSDD : SFOd-DNNF : SFOd-SDNNF : ¬Cd-SDNNF : SFOd-SDNNF$_T$ : ∨BCd-SDNNF$_T$ : SFOdec-DNNF : SFOdec-SDNNF : SFOdec-SDNNF$_T$ : SFOSDD : SFOuFBDD : SFOuOBDD : ¬CuOBDD : SFOuOBDD$_<$ : ∨BCuOBDD$_<$ : SFOd-SDNNF -> SDDd-SDNNF$_T$ -> SDD$_T$

  cSDD : SFOd-DNNF : SFOd-SDNNF : ¬Cd-SDNNF : SFOd-SDNNF$_T$ : ∨BCd-SDNNF$_T$ : SFOdec-DNNF : SFOdec-SDNNF : SFOdec-SDNNF$_T$ : SFOSDD : SFOuFBDD : SFOuOBDD : ¬CuOBDD : SFOuOBDD$_<$ : ∨BCuOBDD$_<$ : SFOd-SDNNF -> SDDd-SDNNF$_T$ -> SDD$_T$ +
  bib
• [bib] 1987
  Ingo Wegener, "The Complexity of Boolean Functions," 1987. Wegener_1987

  dec-DNNF : ∨CFBDD : ∧CFBDD : ∨COBDD : ∧CIP -> FBDDMODS -> IPPI -> FBDD

  dec-DNNF : ∨CFBDD : ∧CFBDD : ∨COBDD : ∧CIP -> FBDDMODS -> IPPI -> FBDD +
  bib
• [bib] 2000
  I. Wegener, "Branching Programs and Binary Decision Diagrams: Theory and Applications," 2000. Wegener_2000

  cSDD$_T$ : ∧Cd-SDNNF$_T$ : ∧Cdec-DNNF : CDdec-SDNNF : CDdec-SDNNF$_T$ : CDFBDD : SFOnFBDD : ¬CnFBDD : CDnOBDD : ¬CnOBDD : CDnOBDD$_<$ : ¬CnOBDD$_<$ : ∧BCnOBDD$_<$ : ∧CnOBDD$_<$ : CDSDD$_T$ : ∧CSDNNF : ¬CSDNNF$_T$ : ¬CTDD$_T$ : ∧CuFBDD : CDuOBDD : CDuOBDD$_<$ : ∧BCuOBDD$_<$ : ∧CuOBDD$_<$ : CDcSDD$_T$ -> OBDD$_<$d-SDNNF -> uOBDDd-SDNNF$_T$ -> nFBDDd-SDNNF$_T$ -> uOBDD$_<$DNF -> nOBDD$_<$DNNF -> nFBDDnOBDD$_<$ -> nOBDDOBDD -> OBDD$_<$OBDD$_<$ -> uOBDD$_<$SDNNF -> nOBDDSDNNF$_T$ -> nOBDD$_<$uFBDD -> FBDDuOBDD -> FBDDuOBDD -> OBDDuOBDD$_<$ -> nOBDD$_<$uOBDD$_<$ -> uOBDD

  cSDD$_T$ : ∧Cd-SDNNF$_T$ : ∧Cdec-DNNF : CDdec-SDNNF : CDdec-SDNNF$_T$ : CDFBDD : SFOnFBDD : ¬CnFBDD : CDnOBDD : ¬CnOBDD : CDnOBDD$_<$ : ¬CnOBDD$_<$ : ∧BCnOBDD$_<$ : ∧CnOBDD$_<$ : CDSDD$_T$ : ∧CSDNNF : ¬CSDNNF$_T$ : ¬CTDD$_T$ : ∧CuFBDD : CDuOBDD : CDuOBDD$_<$ : ∧BCuOBDD$_<$ : ∧CuOBDD$_<$ : CDcSDD$_T$ -> OBDD$_<$d-SDNNF -> uOBDDd-SDNNF$_T$ -> nFBDDd-SDNNF$_T$ -> uOBDD$_<$DNF -> nOBDD$_<$DNNF -> nFBDDnOBDD$_<$ -> nOBDDOBDD -> OBDD$_<$OBDD$_<$ -> uOBDD$_<$SDNNF -> nOBDDSDNNF$_T$ -> nOBDD$_<$uFBDD -> FBDDuOBDD -> FBDDuOBDD -> OBDDuOBDD$_<$ -> nOBDD$_<$uOBDD$_<$ -> uOBDD +
  bib