← Back to Zoo

Bibliography

46 references used across the Tractable Circuit Zoo

46 results

[1] 2018
A. Amarilli and F. Capelli and M. Monet and P. Senellart, "Connecting Knowledge Compilation Classes and Width Parameters", CoRR, vol. abs/1811.02944, 2018. Amarilli_2018
cSDD : ∧BC cSDD : ∧C cSDD : ∨BC cSDD : ∨C cSDD $_T$ : ∧C cSDD $_T$ : ∨C cSDD $_T$ : FO d-DNNF : ∧BC d-DNNF : ∨BC d-SDNNF : ∧BC d-SDNNF : ∧C d-SDNNF : ∨BC d-SDNNF : ∨C d-SDNNF $_T$ : ∧C d-SDNNF $_T$ : ∨C dec-DNNF : ∧BC dec-DNNF : ∧C dec-DNNF : ∨BC dec-DNNF : ∨C dec-SDNNF : ∧BC dec-SDNNF : ∧C dec-SDNNF : ∨BC dec-SDNNF : ∨C dec-SDNNF $_T$ : ∧C dec-SDNNF $_T$ : ∨C DNNF : ∧BC nFBDD : ¬C nFBDD : ∧BC nFBDD : ∧C nOBDD : ¬C nOBDD : ∧BC nOBDD : ∧C nOBDD : ∨BC nOBDD $_<$ : ¬C nOBDD $_<$ : ∧C OBDD : ∧BC OBDD : ∧C OBDD : ∨BC OBDD $_<$ : ∨C OBDD $_<$ : FO SDD : ∧BC SDD : ∧C SDD : ∨BC SDD $_T$ : ∧C SDD $_T$ : ∨C SDD $_T$ : FO SDNNF : ¬C SDNNF : ∧BC SDNNF : ∧C SDNNF : ∨BC SDNNF $_T$ : ¬C SDNNF $_T$ : ∧C TDD : ∧BC TDD : ∧C TDD : ∨BC TDD : ∨C TDD : FO TDD $_T$ : ∧C TDD $_T$ : ∨C TDD $_T$ : FO uFBDD : ∧BC uFBDD : ∧C uFBDD : ∨BC uOBDD : ∧BC uOBDD : ∧C uOBDD : ∨BC uOBDD : ∨C uOBDD $_<$ : ∧C uOBDD $_<$ : ∨C d-SDNNF -> d-DNNF d-SDNNF -> SDNNF d-SDNNF -> uOBDD d-SDNNF $_T$ -> nFBDD d-SDNNF $_T$ -> SDNNF $_T$ d-SDNNF $_T$ -> uOBDD $_<$ dec-DNNF -> d-DNNF dec-DNNF -> FBDD dec-SDNNF -> d-SDNNF dec-SDNNF -> dec-DNNF dec-SDNNF -> OBDD dec-SDNNF $_T$ -> d-SDNNF $_T$ dec-SDNNF $_T$ -> dec-SDNNF dec-SDNNF $_T$ -> nFBDD dec-SDNNF $_T$ -> OBDD $_<$ DNF -> d-SDNNF DNF -> nOBDD $_<$ DNNF -> nFBDD FBDD -> dec-DNNF FBDD -> uFBDD nFBDD -> d-DNNF nFBDD -> DNNF nFBDD -> FBDD nFBDD -> uFBDD nOBDD -> nFBDD nOBDD -> SDNNF nOBDD $_<$ -> SDNNF $_T$ OBDD -> dec-SDNNF OBDD -> uOBDD OBDD $_<$ -> dec-SDNNF $_T$ OBDD $_<$ -> uOBDD $_<$ SDNNF -> DNNF SDNNF -> nOBDD SDNNF $_T$ -> nOBDD $_<$ uFBDD -> d-DNNF uFBDD -> FBDD uFBDD -> nFBDD uOBDD -> d-SDNNF uOBDD -> nOBDD uOBDD -> uFBDD uOBDD $_<$ -> d-SDNNF $_T$ uOBDD $_<$ -> nOBDD $_<$

cSDD : ∧BCcSDD : ∧CcSDD : ∨BCcSDD : ∨CcSDD $_T$ : ∧CcSDD $_T$ : ∨CcSDD $_T$ : FOd-DNNF : ∧BCd-DNNF : ∨BCd-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$ : ∨CDNNF : ∧BCnFBDD : ¬CnFBDD : ∧BCnFBDD : ∧CnOBDD : ¬CnOBDD : ∧BCnOBDD : ∧CnOBDD : ∨BCnOBDD $_<$ : ¬CnOBDD $_<$ : ∧COBDD : ∧BCOBDD : ∧COBDD : ∨BCOBDD $_<$ : ∨COBDD $_<$ : FOSDD : ∧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 $_<$
[2] 2013
P. Beame and J. Li and S. Roy and D. Suciu, "Model Counting of Query Expressions: Limitations of Propositional Methods", 2013. Beame_2013
dec-DNNF : ∨C dec-SDNNF : ∧C dec-SDNNF : ∨C dec-SDNNF $_T$ : ∧C dec-SDNNF $_T$ : ∨C dec-DNNF -> FBDD dec-SDNNF -> OBDD dec-SDNNF $_T$ -> nFBDD dec-SDNNF $_T$ -> OBDD $_<$
[3] 2015
P. Beame and V. Liew, "New Limits for Knowledge Compilation and Applications to Exact Model Counting", 2015. Beame_2015
dec-SDNNF : ∧C dec-SDNNF : ∨C dec-SDNNF $_T$ : ∧C dec-SDNNF $_T$ : ∨C d-SDNNF -> uOBDD d-SDNNF $_T$ -> nFBDD d-SDNNF $_T$ -> uOBDD $_<$ dec-SDNNF -> OBDD dec-SDNNF $_T$ -> OBDD $_<$ DNNF -> nFBDD FBDD -> SDD SDNNF -> nOBDD SDNNF $_T$ -> nOBDD $_<$
[4] 1980
M. Blum and 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
[5] 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
DNNF -> nFBDD
[6] 2018
B. Bollig and M. Buttkus, "On the Relative Succinctness of Sentential Decision Diagrams", 2018. Bollig_2018
dec-SDNNF : ∧C dec-SDNNF : ∨C dec-SDNNF $_T$ : ∧C dec-SDNNF $_T$ : ∨C d-SDNNF -> uOBDD d-SDNNF $_T$ -> nFBDD d-SDNNF $_T$ -> uOBDD $_<$ dec-SDNNF -> OBDD dec-SDNNF $_T$ -> OBDD $_<$ DNNF -> nFBDD SDD $_T$ -> FBDD SDNNF -> nOBDD SDNNF $_T$ -> nOBDD $_<$
[7] 2014
S. Bova and F. Capelli and S. Mengel and F. Slivovsky, "Expander CNFs have exponential DNNF size", 2014. Bova_2014
cSDD : ∧C cSDD $_T$ : ∧C d-SDNNF : ∧C d-SDNNF $_T$ : ∧C dec-DNNF : ∧C dec-SDNNF : ∧C dec-SDNNF $_T$ : ∧C DNF : ¬C DNF : ∧C DNNF : ¬C DNNF : ∧C FBDD : ∧C nFBDD : ¬C nFBDD : ∧C nOBDD : ¬C nOBDD : ∧C nOBDD $_<$ : ¬C nOBDD $_<$ : ∧C OBDD : ∧C SDD : ∧C SDD $_T$ : ∧C SDNNF : ¬C SDNNF : ∧C SDNNF $_T$ : ¬C SDNNF $_T$ : ∧C TDD : ∧C TDD $_T$ : ∧C uFBDD : ∧C uOBDD : ∧C uOBDD $_<$ : ∧C CNF -> DNNF

cSDD : ∧CcSDD $_T$ : ∧Cd-SDNNF : ∧Cd-SDNNF $_T$ : ∧Cdec-DNNF : ∧Cdec-SDNNF : ∧Cdec-SDNNF $_T$ : ∧CDNF : ¬CDNF : ∧CDNNF : ¬CDNNF : ∧CFBDD : ∧CnFBDD : ¬CnFBDD : ∧CnOBDD : ¬CnOBDD : ∧CnOBDD $_<$ : ¬CnOBDD $_<$ : ∧COBDD : ∧CSDD : ∧CSDD $_T$ : ∧CSDNNF : ¬CSDNNF : ∧CSDNNF $_T$ : ¬CSDNNF $_T$ : ∧CTDD : ∧CTDD $_T$ : ∧CuFBDD : ∧CuOBDD : ∧CuOBDD $_<$ : ∧CCNF -> DNNF
[8] 2016
S. Bova and F. Capelli and 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 : ∨BC dec-DNNF : ∨BC FBDD : ∨BC uFBDD : ∨BC DNNF -> d-DNNF PI -> DNNF uFBDD -> FBDD
[9] 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 -> OBDD cSDD $_T$ -> OBDD cSDD $_T$ -> OBDD $_<$
[10] 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 : CT OBDD $_<$ : CO OBDD $_<$ : CT OBDD $_<$ : EQ OBDD $_<$ : ME OBDD $_<$ : VA OBDD $_<$ : ¬C OBDD $_<$ : ∧BC OBDD $_<$ : ∨BC OBDD $_<$ : CD cSDD $_T$ -> OBDD $_<$ uOBDD -> OBDD
[11] 1992
R. E. Bryant, "Symbolic Boolean manipulation with ordered binary-decision diagrams", ACM Computing Surveys, vol. 24, pp. 293–318, 1992. Bryant_1992
FBDD : CO FBDD : CT FBDD : VA OBDD $_<$ : EQ
[12] 2016
F. Capelli, "Structural Restrictions of CNF-formulas: Applications to Model Counting and Knowledge Compilation", 2016. Capelli_2016
FBDD -> SDNNF
[13] 2026
F. Capelli and Y. Choi and S. Mengel and M. Muñoz and G. Van den Broeck, "A canonical generalization of OBDD", 2026. Capelli_2026
d-DNNF : ∧BC d-DNNF : ∨BC d-SDNNF : ∧BC d-SDNNF : ∨BC DNNF : ∧BC OBDD : ∧BC OBDD : ∨BC SDD : ∧BC SDD : ∨BC SDNNF : ∧BC SDNNF : ∨BC TDD : ¬C TDD : ∧BC TDD : ∧C TDD : ∨BC TDD : ∨C TDD : CD TDD : FO TDD : SFO TDD $_T$ : ¬C TDD $_T$ : ∧BC TDD $_T$ : ∧C TDD $_T$ : ∨C TDD $_T$ : CD TDD $_T$ : FO OBDD -> TDD OBDD $_<$ -> TDD $_T$ TDD -> d-SDNNF TDD -> SDD TDD $_T$ -> d-SDNNF $_T$ TDD $_T$ -> OBDD TDD $_T$ -> SDD $_T$ TDD $_T$ -> TDD

d-DNNF : ∧BCd-DNNF : ∨BCd-SDNNF : ∧BCd-SDNNF : ∨BCDNNF : ∧BCOBDD : ∧BCOBDD : ∨BCSDD : ∧BCSDD : ∨BCSDNNF : ∧BCSDNNF : ∨BCTDD : ¬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
[14] 1978
A. K. Chandra and G. Markowsky, "On the Number of Prime Implicants", Discrete Mathematics, vol. 24, pp. 7–11, 1978. Chandra_1978
[15] 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
[16] 2000
A. Darwiche, "On the tractable counting of theory models and its application to belief revision and truth maintenance", 2000. Darwiche_2000
d-DNNF -> FBDD
[17] 2001
A. Darwiche, "Decomposable Negation Normal Form", Journal of the ACM, vol. 48, pp. 608–647, 2001. Darwiche_2001a
DNNF : CO d-DNNF : ∧BC DNNF : FO
[18] 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
[19] 2002
A. Darwiche and P. Marquis, "A Knowledge Compilation Map", Journal of Artificial Intelligence Research, vol. 17, pp. 229–264, 2002. Darwiche_2002
CNF : IM CNF : VA DNF : VA DNNF : CO IP : CT IP : IM IP : SE MODS : CO MODS : CT OBDD : CT OBDD : EQ OBDD : SE PI : CE PI : CT PI : SE CNF : ∧C CNF : ∨BC CNF : ∨C CNF : CD CNF : FO cSDD : ∧C cSDD : ∨C cSDD $_T$ : ∧C cSDD $_T$ : ∨C cSDD $_T$ : FO d-DNNF : ∧BC d-DNNF : CD d-SDNNF : ∧C d-SDNNF : ∨C d-SDNNF $_T$ : ∧C d-SDNNF $_T$ : ∨C dec-DNNF : ∧BC dec-DNNF : ∧C dec-DNNF : ∨C dec-SDNNF : ∧BC dec-SDNNF : ∧C dec-SDNNF : ∨C dec-SDNNF $_T$ : ∧C dec-SDNNF $_T$ : ∨C DNF : ¬C DNF : ∧BC DNF : ∧C DNF : ∨C DNNF : ¬C DNNF : ∧C DNNF : ∨C DNNF : CD FBDD : ¬C FBDD : ∧BC FBDD : ∧C FBDD : ∨BC FBDD : ∨C FBDD : CD IP : ¬C IP : ∧BC IP : ∧C IP : ∨BC IP : CD IP : SFO MODS : ¬C MODS : ∧BC MODS : ∧C MODS : ∨BC MODS : FO nFBDD : ∧C NNF : ¬C NNF : ∧C NNF : CD NNF : FO nOBDD : ∧C nOBDD $_<$ : ∧C OBDD : ¬C OBDD : ∧C OBDD : ∨C OBDD : CD OBDD : FO OBDD : SFO OBDD $_<$ : ∨C OBDD $_<$ : FO PI : ¬C PI : ∧BC PI : ∨BC PI : ∨C PI : CD PI : FO SDD : ∧C SDD $_T$ : ∧C SDD $_T$ : ∨C SDD $_T$ : FO SDNNF : ∧C SDNNF $_T$ : ∧C TDD : ∧C TDD : ∨C TDD : FO TDD $_T$ : ∧C TDD $_T$ : ∨C TDD $_T$ : FO uFBDD : ∧C uOBDD : ∧C uOBDD : ∨C uOBDD $_<$ : ∧C uOBDD $_<$ : ∨C CNF -> NNF CNF -> PI d-DNNF -> DNNF d-DNNF -> MODS dec-SDNNF -> OBDD dec-SDNNF $_T$ -> OBDD $_<$ DNF -> d-DNNF DNF -> DNNF DNF -> IP DNNF -> nFBDD DNNF -> NNF FBDD -> d-DNNF IP -> CNF IP -> DNF IP -> FBDD IP -> MODS MODS -> CNF MODS -> d-DNNF MODS -> DNF MODS -> OBDD $_<$ OBDD -> FBDD OBDD $_<$ -> CNF OBDD $_<$ -> DNF OBDD $_<$ -> OBDD PI -> CNF PI -> DNF PI -> FBDD PI -> MODS

CNF : IMCNF : VADNF : VADNNF : COIP : CTIP : IMIP : SEMODS : COMODS : CTOBDD : CTOBDD : EQOBDD : SEPI : CEPI : CTPI : SECNF : ∧CCNF : ∨BCCNF : ∨CCNF : CDCNF : FOcSDD : ∧CcSDD : ∨CcSDD $_T$ : ∧CcSDD $_T$ : ∨CcSDD $_T$ : FOd-DNNF : ∧BCd-DNNF : CDd-SDNNF : ∧Cd-SDNNF : ∨Cd-SDNNF $_T$ : ∧Cd-SDNNF $_T$ : ∨Cdec-DNNF : ∧BCdec-DNNF : ∧Cdec-DNNF : ∨Cdec-SDNNF : ∧BCdec-SDNNF : ∧Cdec-SDNNF : ∨Cdec-SDNNF $_T$ : ∧Cdec-SDNNF $_T$ : ∨CDNF : ¬CDNF : ∧BCDNF : ∧CDNF : ∨CDNNF : ¬CDNNF : ∧CDNNF : ∨CDNNF : CDFBDD : ¬CFBDD : ∧BCFBDD : ∧CFBDD : ∨BCFBDD : ∨CFBDD : CDIP : ¬CIP : ∧BCIP : ∧CIP : ∨BCIP : CDIP : SFOMODS : ¬CMODS : ∧BCMODS : ∧CMODS : ∨BCMODS : FOnFBDD : ∧CNNF : ¬CNNF : ∧CNNF : CDNNF : FOnOBDD : ∧CnOBDD $_<$ : ∧COBDD : ¬COBDD : ∧COBDD : ∨COBDD : CDOBDD : FOOBDD : SFOOBDD $_<$ : ∨COBDD $_<$ : FOPI : ¬CPI : ∧BCPI : ∨BCPI : ∨CPI : CDPI : FOSDD : ∧CSDD $_T$ : ∧CSDD $_T$ : ∨CSDD $_T$ : FOSDNNF : ∧CSDNNF $_T$ : ∧CTDD : ∧CTDD : ∨CTDD : FOTDD $_T$ : ∧CTDD $_T$ : ∨CTDD $_T$ : FOuFBDD : ∧CuOBDD : ∧CuOBDD : ∨CuOBDD $_<$ : ∧CuOBDD $_<$ : ∨CCNF -> NNFCNF -> PId-DNNF -> DNNFd-DNNF -> MODSdec-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 -> MODS
[20] 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 : ∧BC cSDD : ∨BC cSDD $_T$ : ∧C cSDD $_T$ : ∨C cSDD $_T$ : FO dec-SDNNF : ∧C dec-SDNNF : ∨C dec-SDNNF $_T$ : ∧C dec-SDNNF $_T$ : ∨C OBDD : ∧C OBDD $_<$ : ∨C OBDD $_<$ : FO SDD : ¬C SDD : CD SDD $_T$ : ¬C SDD $_T$ : ∧BC SDD $_T$ : ∧C SDD $_T$ : ∨BC SDD $_T$ : ∨C SDD $_T$ : CD SDD $_T$ : FO cSDD $_T$ -> cSDD OBDD -> cSDD OBDD $_<$ -> cSDD $_T$ SDD $_T$ -> SDD

cSDD : ∧BCcSDD : ∨BCcSDD $_T$ : ∧CcSDD $_T$ : ∨CcSDD $_T$ : FOdec-SDNNF : ∧Cdec-SDNNF : ∨Cdec-SDNNF $_T$ : ∧Cdec-SDNNF $_T$ : ∨COBDD : ∧COBDD $_<$ : ∨COBDD $_<$ : FOSDD : ¬CSDD : CDSDD $_T$ : ¬CSDD $_T$ : ∧BCSDD $_T$ : ∧CSDD $_T$ : ∨BCSDD $_T$ : ∨CSDD $_T$ : CDSDD $_T$ : FOcSDD $_T$ -> cSDDOBDD -> cSDDOBDD $_<$ -> cSDD $_T$ SDD $_T$ -> SDD
[21] 2002
A. Darwiche and J. Huang, "Testing equivalence probabilistically", 2002. Darwiche_Huang_2002
d-DNNF : EQ
[22] 2007
J. Huang and A. Darwiche, "The Language of Search", Journal of Artificial Intelligence Research, vol. 29, pp. 191–219, 2007. darwiche2007language
[23] 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 : ∨C OBDD : FO DNF -> OBDD
[24] 2013
H. Fargier and 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
[25] 1978
S. Fortune and 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
[26] 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 : CO FBDD : CT FBDD : VA FBDD -> OBDD
[27] 1995
G. Gogic and H. Kautz and 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
[28] 2002
S. Jukna and G. Schnitger, "Triangle-Freeness is Hard to Detect", Combinatorics, Probability and Computing, vol. 11, pp. 549–569, 2002. Jukna_2002
[29] 2016
N. S. Kaleyski, "Boolean methods in knowledge compilation", 2016. Kaleyski_2016
MODS -> PI
[30] 2003
J. Lang and 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
[31] 1973
L. A. Levin, "Universal Search Problems", Problems of Information Transmission, vol. 9, pp. 265–266, 1973. Levin_1973
CNF : CO
[32] 2000
P. Marquis, "Consequence Finding Algorithms", Handbook of Defeasible Reasoning and Uncertainty Management Systems, vol. 5, pp. 41–145, 2000. Marquis_2000
[33] 1998
C. Meinel and T. Theobald, "Algorithms and Data Structures in VLSI Design: OBDD - Foundations and Applications", 1998. Meinel_Theobald_1998
OBDD : EQ OBDD : SE OBDD $_<$ : EQ
[34] 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 : CD d-SDNNF : FO d-SDNNF $_T$ : ∧BC d-SDNNF $_T$ : ∧C d-SDNNF $_T$ : ∨C d-SDNNF $_T$ : CD nOBDD $_<$ : ¬C nOBDD $_<$ : ∧C SDNNF : ¬C SDNNF : CD SDNNF : FO SDNNF $_T$ : ¬C SDNNF $_T$ : ∧BC SDNNF $_T$ : ∧C SDNNF $_T$ : ∨C SDNNF $_T$ : CD SDNNF $_T$ : FO d-SDNNF -> uOBDD d-SDNNF $_T$ -> d-SDNNF DNNF -> nFBDD SDNNF -> nOBDD SDNNF $_T$ -> SDNNF
[35] 2010
T. Pipatsrisawat, "Reasoning with Propositional Knowledge: Frameworks for Boolean Satisfiability and Knowledge Compilation", 2010. Pipatsrisawat_2010
FBDD -> SDNNF
[36] 1952
W. V. Quine, "The Problem of Simplifying Truth Functions", The American Mathematical Monthly, vol. 59, pp. 521–531, 1952. Quine_1952
[37] 1996
D. Roth, "On the Hardness of Approximate Reasoning", Artificial Intelligence, vol. 82, pp. 273–302, 1996. Roth_1996
PI : CT
[38] 2003
M. Sauerhoff, "Approximation of boolean functions by combinatorial rectangles", Theoretical Computer Science, vol. 301, pp. 45–78, 2003. Sauerhoff_2003
[39] 1996
P. Savicky and S. Zak, "A Large Lower Bound for 1-Branching Programs", 1996. Savicky_Zak_1996
uOBDD -> FBDD
[40] 1996
B. Selman and H. Kautz, "Knowledge compilation and theory approximation", J. ACM, vol. 43, pp. 193–224, 1996. Selman_1996
[41] 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
[42] —
D. Kahdian and O. Broadrick and R. Geh and G. Van den Broeck, "A Tractable Circuit Zoo", forthcoming. TCZ_Forthcoming
cSDD : ∧BC cSDD : ∧C cSDD : ∨BC cSDD : ∨C cSDD : SFO cSDD $_T$ : ∧C cSDD $_T$ : ∨C d-DNNF : ∧BC d-DNNF : ∨BC d-DNNF : SFO d-SDNNF : ∧BC d-SDNNF : ∧C d-SDNNF : ∨BC d-SDNNF : ∨C d-SDNNF $_T$ : ∧C d-SDNNF $_T$ : ∨C d-SDNNF $_T$ : SFO dec-DNNF : ∧BC dec-DNNF : ∧C dec-DNNF : ∨BC dec-DNNF : ∨C dec-DNNF : SFO dec-SDNNF : ∧BC dec-SDNNF : ∧C dec-SDNNF : ∨BC dec-SDNNF : ∨C dec-SDNNF : SFO dec-SDNNF $_T$ : ∧C dec-SDNNF $_T$ : ∨C dec-SDNNF $_T$ : SFO DNF : ∧C DNNF : ∧BC DNNF : ∧C FBDD : ∧BC FBDD : ∧C FBDD : ∨BC FBDD : ∨C nFBDD : ∧BC nFBDD : ∧C nFBDD : ∨C nFBDD : FO nOBDD : ∧BC nOBDD : ∧C nOBDD : ∨BC nOBDD : FO nOBDD $_<$ : ∧C nOBDD $_<$ : ∨C nOBDD $_<$ : FO OBDD : ∧BC OBDD : ∧C OBDD : ∨BC OBDD : ∨C OBDD $_<$ : ∨C SDD : ∧BC SDD : ∧C SDD : ∨BC SDD : SFO SDD $_T$ : ∧C SDD $_T$ : ∨C SDNNF : ∧BC SDNNF : ∧C SDNNF : ∨BC SDNNF $_T$ : ∧C TDD : ∧BC TDD : ∧C TDD : ∨BC TDD : ∨C TDD $_T$ : ∧C TDD $_T$ : ∨C uFBDD : ∧BC uFBDD : ∧C uFBDD : ∨BC uFBDD : SFO uOBDD : ∧BC uOBDD : ∧C uOBDD : ∨BC uOBDD : ∨C uOBDD $_<$ : ∧C uOBDD $_<$ : ∨C uOBDD $_<$ : SFO d-SDNNF -> uOBDD d-SDNNF $_T$ -> nFBDD d-SDNNF $_T$ -> uOBDD $_<$ dec-SDNNF $_T$ -> OBDD $_<$ DNNF -> nFBDD OBDD -> SDNNF $_T$ SDNNF -> nOBDD SDNNF $_T$ -> nOBDD $_<$

cSDD : ∧BCcSDD : ∧CcSDD : ∨BCcSDD : ∨CcSDD : SFOcSDD $_T$ : ∧CcSDD $_T$ : ∨Cd-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 $_<$ : ∨CSDD : ∧BCSDD : ∧CSDD : ∨BCSDD : SFOSDD $_T$ : ∧CSDD $_T$ : ∨CSDNNF : ∧BCSDNNF : ∧CSDNNF : ∨BCSDNNF $_T$ : ∧CTDD : ∧BCTDD : ∧CTDD : ∨BCTDD : ∨CTDD $_T$ : ∧CTDD $_T$ : ∨CuFBDD : ∧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 $_<$
[43] 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 : ¬C cSDD : ∧BC cSDD : ∧C cSDD : ∨BC cSDD : ∨C cSDD $_T$ : ¬C cSDD $_T$ : ∧BC cSDD $_T$ : ∧C cSDD $_T$ : ∨C cSDD $_T$ : CD cSDD $_T$ : FO cSDD $_T$ : SFO dec-SDNNF : ∧C dec-SDNNF : ∨C dec-SDNNF $_T$ : ∧C dec-SDNNF $_T$ : ∨C OBDD : ∧C OBDD : FO OBDD $_<$ : ∨C OBDD $_<$ : FO SDD : ∧BC SDD : ∧C SDD : ∨BC SDD $_T$ : ∧C SDD $_T$ : ∨C SDD $_T$ : FO TDD : FO TDD $_T$ : FO cSDD -> SDD cSDD $_T$ -> SDD $_T$ SDD -> d-SDNNF SDD $_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$ : SFOdec-SDNNF : ∧Cdec-SDNNF : ∨Cdec-SDNNF $_T$ : ∧Cdec-SDNNF $_T$ : ∨COBDD : ∧COBDD : FOOBDD $_<$ : ∨COBDD $_<$ : 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$
[44] 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
d-SDNNF : ¬C d-SDNNF : SFO d-SDNNF $_T$ : ∨BC uOBDD : ¬C uOBDD : SFO uOBDD $_<$ : ∨BC d-SDNNF -> SDD d-SDNNF $_T$ -> SDD $_T$
[45] 1987
I. Wegener, "The Complexity of Boolean Functions", 1987. Wegener_1987
dec-DNNF : ∨C FBDD : ∨C IP -> FBDD MODS -> IP PI -> FBDD
[46] 2000
I. Wegener, "Branching Programs and Binary Decision Diagrams: Theory and Applications", 2000. Wegener_2000
dec-DNNF : CD dec-SDNNF : CD dec-SDNNF $_T$ : CD FBDD : SFO nFBDD : ¬C nFBDD : CD nOBDD : ¬C nOBDD : CD nOBDD $_<$ : ¬C nOBDD $_<$ : ∧BC nOBDD $_<$ : CD SDNNF : ¬C SDNNF $_T$ : ¬C uFBDD : CD uOBDD : CD uOBDD $_<$ : ∧BC uOBDD $_<$ : ∧C uOBDD $_<$ : ∨C uOBDD $_<$ : CD cSDD $_T$ -> OBDD $_<$ d-SDNNF -> uOBDD d-SDNNF $_T$ -> nFBDD d-SDNNF $_T$ -> uOBDD $_<$ DNF -> nOBDD $_<$ DNNF -> nFBDD nOBDD $_<$ -> nOBDD OBDD -> OBDD $_<$ OBDD $_<$ -> uOBDD $_<$ SDNNF -> nOBDD SDNNF $_T$ -> nOBDD $_<$ uFBDD -> FBDD uOBDD -> FBDD uOBDD -> OBDD uOBDD $_<$ -> nOBDD $_<$ uOBDD $_<$ -> uOBDD

dec-DNNF : CDdec-SDNNF : CDdec-SDNNF $_T$ : CDFBDD : SFOnFBDD : ¬CnFBDD : CDnOBDD : ¬CnOBDD : CDnOBDD $_<$ : ¬CnOBDD $_<$ : ∧BCnOBDD $_<$ : CDSDNNF : ¬CSDNNF $_T$ : ¬CuFBDD : CDuOBDD : CDuOBDD $_<$ : ∧BCuOBDD $_<$ : ∧CuOBDD $_<$ : ∨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