Bibliography

43 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

  d-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$ -> 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$_<$

  d-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$ -> 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
• [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

  d-DNNF -> dec-DNNFdec-DNNF -> FBDDdec-SDNNF -> OBDDdec-SDNNF$_T$ -> nFBDDdec-SDNNF$_T$ -> OBDD$_<$

  d-DNNF -> dec-DNNFdec-DNNF -> FBDDdec-SDNNF -> OBDDdec-SDNNF$_T$ -> nFBDDdec-SDNNF$_T$ -> OBDD$_<$ +
  bib
• [3] 2015
  P. Beame and V. Liew, "New Limits for Knowledge Compilation and Applications to Exact Model Counting", 2015. Beame_2015

  d-SDNNF -> uOBDDd-SDNNF$_T$ -> nFBDDd-SDNNF$_T$ -> uOBDD$_<$dec-SDNNF -> OBDDdec-SDNNF$_T$ -> OBDD$_<$DNNF -> nFBDDFBDD -> SDDSDNNF -> nOBDDSDNNF$_T$ -> nOBDD$_<$

  d-SDNNF -> uOBDDd-SDNNF$_T$ -> nFBDDd-SDNNF$_T$ -> uOBDD$_<$dec-SDNNF -> OBDDdec-SDNNF$_T$ -> OBDD$_<$DNNF -> nFBDDFBDD -> SDDSDNNF -> nOBDDSDNNF$_T$ -> nOBDD$_<$ +
  bib
• [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

  FBDD : EQ +
  bib
• [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

  DNNF -> nFBDD +
  bib
• [6] 2018
  B. Bollig and M. Buttkus, "On the Relative Succinctness of Sentential Decision Diagrams", 2018. Bollig_2018

  d-SDNNF -> uOBDDd-SDNNF$_T$ -> nFBDDd-SDNNF$_T$ -> uOBDD$_<$dec-SDNNF -> OBDDdec-SDNNF$_T$ -> OBDD$_<$DNNF -> nFBDDSDD$_T$ -> FBDDSDNNF -> nOBDDSDNNF$_T$ -> nOBDD$_<$

  d-SDNNF -> uOBDDd-SDNNF$_T$ -> nFBDDd-SDNNF$_T$ -> uOBDD$_<$dec-SDNNF -> OBDDdec-SDNNF$_T$ -> OBDD$_<$DNNF -> nFBDDSDD$_T$ -> FBDDSDNNF -> nOBDDSDNNF$_T$ -> nOBDD$_<$ +
  bib
• [7] 1847
  G. Boole, "The Mathematical Analysis of Logic: Being an Essay Towards a Calculus of Deductive Reasoning", 1847. Boole_1847
  bib
• [8] 2014
  S. Bova and F. Capelli and S. Mengel and F. Slivovsky, "Expander CNFs have exponential DNNF size", 2014. Bova_2014
  bib
• [9] 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

  DNNF -> d-DNNFPI -> DNNFuFBDD -> FBDD

  DNNF -> d-DNNFPI -> DNNFuFBDD -> FBDD +
  bib
• [10] 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$ -> OBDD$_<$

  cSDD -> OBDDcSDD$_T$ -> OBDD$_<$ +
  bib
• [11] 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$_<$uOBDD -> OBDDuOBDD$_<$ -> OBDD$_<$

  OBDD : CTOBDD$_<$ : COOBDD$_<$ : CTOBDD$_<$ : EQOBDD$_<$ : MEOBDD$_<$ : VAOBDD$_<$ : ¬COBDD$_<$ : ∧BCOBDD$_<$ : ∨BCOBDD$_<$ : CDcSDD$_T$ -> OBDD$_<$uOBDD -> OBDDuOBDD$_<$ -> OBDD$_<$ +
  bib
• [12] 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$_<$ : EQ

  FBDD : COFBDD : CTFBDD : VAOBDD$_<$ : EQ +
  bib
• [13] 1997
  M. Cadoli and F. M. Donini, "A survey on knowledge compilation", AI Communications, vol. 10, pp. 137–150, 1997. Cadoli_1997
  bib
• [14] 2016
  F. Capelli, "Structural Restrictions of CNF-formulas: Applications to Model Counting and Knowledge Compilation", 2016. Capelli_2016

  FBDD -> SDNNF

  FBDD -> SDNNF +
  bib
• [15] 1978
  A. K. Chandra and G. Markowsky, "On the Number of Prime Implicants", Discrete Mathematics, vol. 24, pp. 7–11, 1978. Chandra_1978
  bib
• [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

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

  DNNF : CODNNF : FO

  DNNF : CODNNF : FO +
  bib
• [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

  d-DNNF : CT +
  bib
• [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 : COCNF : IMCNF : VADNF : VADNNF : COIP : CTIP : IMIP : SEMODS : COMODS : CTOBDD : CTOBDD : EQOBDD : SEPI : CEPI : CTPI : SECNF : ∧CCNF : ∨BCCNF : ∨CCNF : CDd-DNNF : ∧BCd-DNNF : CDd-DNNF : SFODNF : ∧BCDNF : ∨CDNNF : ∧BCDNNF : ∨CDNNF : CDFBDD : ¬CFBDD : CDFBDD : SFOIP : ¬CIP : ∧BCIP : ∧CIP : ∨BCIP : CDIP : SFOMODS : ¬CMODS : ∧BCMODS : ∧CMODS : ∨BCMODS : FONNF : ¬CNNF : ∧CNNF : CDOBDD : ¬COBDD : ∧BCOBDD : CDOBDD : SFOPI : ¬CPI : ∧BCPI : ∨BCPI : ∨CPI : CDPI : FOCNF -> 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 -> OBDD$_<$OBDD$_<$ -> CNFOBDD$_<$ -> DNFOBDD$_<$ -> OBDDPI -> CNFPI -> DNFPI -> FBDDPI -> MODS

  CNF : COCNF : IMCNF : VADNF : VADNNF : COIP : CTIP : IMIP : SEMODS : COMODS : CTOBDD : CTOBDD : EQOBDD : SEPI : CEPI : CTPI : SECNF : ∧CCNF : ∨BCCNF : ∨CCNF : CDd-DNNF : ∧BCd-DNNF : CDd-DNNF : SFODNF : ∧BCDNF : ∨CDNNF : ∧BCDNNF : ∨CDNNF : CDFBDD : ¬CFBDD : CDFBDD : SFOIP : ¬CIP : ∧BCIP : ∧CIP : ∨BCIP : CDIP : SFOMODS : ¬CMODS : ∧BCMODS : ∧CMODS : ∨BCMODS : FONNF : ¬CNNF : ∧CNNF : CDOBDD : ¬COBDD : ∧BCOBDD : CDOBDD : SFOPI : ¬CPI : ∧BCPI : ∨BCPI : ∨CPI : CDPI : FOCNF -> 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 -> OBDD$_<$OBDD$_<$ -> CNFOBDD$_<$ -> DNFOBDD$_<$ -> OBDDPI -> CNFPI -> DNFPI -> FBDDPI -> MODS +
  bib
• [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

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

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

  d-DNNF : EQ

  d-DNNF : EQ +
  bib
• [22] 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

  DNF -> OBDD

  DNF -> OBDD +
  bib
• [23] 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

  OBDD : EQ +
  bib
• [24] 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
• [25] 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
  bib
• [26] 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
• [27] 2016
  N. S. Kaleyski, "Boolean methods in knowledge compilation", 2016. Kaleyski_2016

  MODS -> PI

  MODS -> PI +
  bib
• [28] 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

  DNF : FO +
  bib
• [29] 1959
  C. Y. Lee, "Representation of Switching Circuits by Binary-Decision Programs", Bell System Technical Journal, vol. 38, pp. 985–999, 1959. Lee_1959
  bib
• [30] 2000
  P. Marquis, "Consequence Finding Algorithms", Handbook of Defeasible Reasoning and Uncertainty Management Systems, vol. 5, pp. 41–145, 2000. Marquis_2000
  bib
• [31] 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
• [32] 2014
  U. Oztok and A. Darwiche, "On Compiling CNF into Decision-DNNF", International Conference on Principles and Practice of Constraint Programming, pp. 42–57, 2014. Oztok_2014

  dec-DNNF -> FBDDdec-SDNNF -> OBDDdec-SDNNF$_T$ -> dec-SDNNFdec-SDNNF$_T$ -> nFBDDdec-SDNNF$_T$ -> OBDD$_<$

  dec-DNNF -> FBDDdec-SDNNF -> OBDDdec-SDNNF$_T$ -> dec-SDNNFdec-SDNNF$_T$ -> nFBDDdec-SDNNF$_T$ -> OBDD$_<$ +
  bib
• [33] 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$ : CDd-SDNNF$_T$ : FOSDNNF : CDSDNNF : FOSDNNF$_T$ : ∧BCSDNNF$_T$ : ∨CSDNNF$_T$ : CDSDNNF$_T$ : FOd-SDNNF -> uOBDDd-SDNNF$_T$ -> d-SDNNFDNNF -> nFBDDSDNNF -> nOBDDSDNNF$_T$ -> SDNNF

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

  FBDD -> SDNNF

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

  PI : CT

  PI : CT +
  bib
• [37] 2003
  M. Sauerhoff, "Approximation of boolean functions by combinatorial rectangles", Theoretical Computer Science, vol. 301, pp. 45-78, 2003. Sauerhoff_2003
  bib
• [38] 1996
  B. Selman and H. Kautz, "Knowledge compilation and theory approximation", J. ACM, vol. 43, pp. 193–224, 1996. Selman_1996
  bib
• [39] 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$_T$ : ¬CcSDD$_T$ : ∧BCcSDD$_T$ : CDcSDD$_T$ : SFOcSDD -> SDDcSDD$_T$ -> SDD$_T$SDD -> d-SDNNFSDD$_T$ -> d-SDNNF$_T$

  cSDD$_T$ : ¬CcSDD$_T$ : ∧BCcSDD$_T$ : CDcSDD$_T$ : SFOcSDD -> SDDcSDD$_T$ -> SDD$_T$SDD -> d-SDNNFSDD$_T$ -> d-SDNNF$_T$ +
  bib
• [40] 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 : ¬Cd-SDNNF -> SDDd-SDNNF$_T$ -> SDD$_T$

  d-SDNNF : ¬Cd-SDNNF -> SDDd-SDNNF$_T$ -> SDD$_T$ +
  bib
• [41] 1987
  I. Wegener, "The Complexity of Boolean Functions", 1987. Wegener_1987

  IP -> FBDDMODS -> IPPI -> FBDD

  IP -> FBDDMODS -> IPPI -> FBDD +
  bib
• [42] 2000
  I. Wegener, "Branching Programs and Binary Decision Diagrams: Theory and Applications", 2000. Wegener_2000

  cSDD$_T$ -> OBDD$_<$d-SDNNF -> uOBDDd-SDNNF$_T$ -> nFBDDd-SDNNF$_T$ -> uOBDD$_<$DNF -> nOBDD$_<$DNNF -> nFBDDnOBDD$_<$ -> nOBDDOBDD$_<$ -> uOBDD$_<$SDNNF -> nOBDDSDNNF$_T$ -> nOBDD$_<$uFBDD -> FBDDuOBDD -> OBDDuOBDD$_<$ -> nOBDD$_<$uOBDD$_<$ -> OBDD$_<$uOBDD$_<$ -> uOBDD

  cSDD$_T$ -> OBDD$_<$d-SDNNF -> uOBDDd-SDNNF$_T$ -> nFBDDd-SDNNF$_T$ -> uOBDD$_<$DNF -> nOBDD$_<$DNNF -> nFBDDnOBDD$_<$ -> nOBDDOBDD$_<$ -> uOBDD$_<$SDNNF -> nOBDDSDNNF$_T$ -> nOBDD$_<$uFBDD -> FBDDuOBDD -> OBDDuOBDD$_<$ -> nOBDD$_<$uOBDD$_<$ -> OBDD$_<$uOBDD$_<$ -> uOBDD +
  bib
• [43] 1927
  I. I. Zhegalkin, "On the Technique of Calculating Propositions in Symbolic Logic", Matematicheskii Sbornik, vol. 34, pp. 9–28, 1927. Zhegalkin_1927
  bib