← Back to Zoo
Bibliography
43 references used across the Tractable Circuit Zoo
A–Z
Year
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-DNNF
d-SDNNF
->
SDNNF
d-SDNNF
->
uOBDD
d-SDNNF
T
_T
T
->
nFBDD
d-SDNNF
T
_T
T
->
SDNNF
T
_T
T
d-SDNNF
T
_T
T
->
uOBDD
<
_<
<
dec-DNNF
->
d-DNNF
dec-DNNF
->
FBDD
dec-SDNNF
->
d-SDNNF
dec-SDNNF
->
dec-DNNF
dec-SDNNF
->
OBDD
dec-SDNNF
T
_T
T
->
d-SDNNF
T
_T
T
dec-SDNNF
T
_T
T
->
nFBDD
dec-SDNNF
T
_T
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
_T
T
OBDD
->
dec-SDNNF
OBDD
->
uOBDD
OBDD
<
_<
<
->
dec-SDNNF
T
_T
T
OBDD
<
_<
<
->
uOBDD
<
_<
<
SDNNF
->
DNNF
SDNNF
->
nOBDD
SDNNF
T
_T
T
->
nOBDD
<
_<
<
uFBDD
->
d-DNNF
uFBDD
->
FBDD
uFBDD
->
nFBDD
uOBDD
->
d-SDNNF
uOBDD
->
nOBDD
uOBDD
->
uFBDD
uOBDD
<
_<
<
->
d-SDNNF
T
_T
T
uOBDD
<
_<
<
->
nOBDD
<
_<
<
d-SDNNF
->
d-DNNF
d-SDNNF
->
SDNNF
d-SDNNF
->
uOBDD
d-SDNNF
T
_T
T
->
nFBDD
d-SDNNF
T
_T
T
->
SDNNF
T
_T
T
d-SDNNF
T
_T
T
->
uOBDD
<
_<
<
dec-DNNF
->
d-DNNF
dec-DNNF
->
FBDD
dec-SDNNF
->
d-SDNNF
dec-SDNNF
->
dec-DNNF
dec-SDNNF
->
OBDD
dec-SDNNF
T
_T
T
->
d-SDNNF
T
_T
T
dec-SDNNF
T
_T
T
->
nFBDD
dec-SDNNF
T
_T
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
_T
T
OBDD
->
dec-SDNNF
OBDD
->
uOBDD
OBDD
<
_<
<
->
dec-SDNNF
T
_T
T
OBDD
<
_<
<
->
uOBDD
<
_<
<
SDNNF
->
DNNF
SDNNF
->
nOBDD
SDNNF
T
_T
T
->
nOBDD
<
_<
<
uFBDD
->
d-DNNF
uFBDD
->
FBDD
uFBDD
->
nFBDD
uOBDD
->
d-SDNNF
uOBDD
->
nOBDD
uOBDD
->
uFBDD
uOBDD
<
_<
<
->
d-SDNNF
T
_T
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-DNNF
dec-DNNF
->
FBDD
dec-SDNNF
->
OBDD
dec-SDNNF
T
_T
T
->
nFBDD
dec-SDNNF
T
_T
T
->
OBDD
<
_<
<
d-DNNF
->
dec-DNNF
dec-DNNF
->
FBDD
dec-SDNNF
->
OBDD
dec-SDNNF
T
_T
T
->
nFBDD
dec-SDNNF
T
_T
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
->
uOBDD
d-SDNNF
T
_T
T
->
nFBDD
d-SDNNF
T
_T
T
->
uOBDD
<
_<
<
dec-SDNNF
->
OBDD
dec-SDNNF
T
_T
T
->
OBDD
<
_<
<
DNNF
->
nFBDD
FBDD
->
SDD
SDNNF
->
nOBDD
SDNNF
T
_T
T
->
nOBDD
<
_<
<
d-SDNNF
->
uOBDD
d-SDNNF
T
_T
T
->
nFBDD
d-SDNNF
T
_T
T
->
uOBDD
<
_<
<
dec-SDNNF
->
OBDD
dec-SDNNF
T
_T
T
->
OBDD
<
_<
<
DNNF
->
nFBDD
FBDD
->
SDD
SDNNF
->
nOBDD
SDNNF
T
_T
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
->
uOBDD
d-SDNNF
T
_T
T
->
nFBDD
d-SDNNF
T
_T
T
->
uOBDD
<
_<
<
dec-SDNNF
->
OBDD
dec-SDNNF
T
_T
T
->
OBDD
<
_<
<
DNNF
->
nFBDD
SDD
T
_T
T
->
FBDD
SDNNF
->
nOBDD
SDNNF
T
_T
T
->
nOBDD
<
_<
<
d-SDNNF
->
uOBDD
d-SDNNF
T
_T
T
->
nFBDD
d-SDNNF
T
_T
T
->
uOBDD
<
_<
<
dec-SDNNF
->
OBDD
dec-SDNNF
T
_T
T
->
OBDD
<
_<
<
DNNF
->
nFBDD
SDD
T
_T
T
->
FBDD
SDNNF
->
nOBDD
SDNNF
T
_T
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-DNNF
PI
->
DNNF
uFBDD
->
FBDD
DNNF
->
d-DNNF
PI
->
DNNF
uFBDD
->
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
->
OBDD
cSDD
T
_T
T
->
OBDD
<
_<
<
cSDD
->
OBDD
cSDD
T
_T
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
:
CT
OBDD
<
_<
<
:
CO
OBDD
<
_<
<
:
CT
OBDD
<
_<
<
:
EQ
OBDD
<
_<
<
:
ME
OBDD
<
_<
<
:
VA
OBDD
<
_<
<
:
¬C
OBDD
<
_<
<
:
∧BC
OBDD
<
_<
<
:
∨BC
OBDD
<
_<
<
:
CD
cSDD
T
_T
T
->
OBDD
<
_<
<
uOBDD
->
OBDD
uOBDD
<
_<
<
->
OBDD
<
_<
<
OBDD
:
CT
OBDD
<
_<
<
:
CO
OBDD
<
_<
<
:
CT
OBDD
<
_<
<
:
EQ
OBDD
<
_<
<
:
ME
OBDD
<
_<
<
:
VA
OBDD
<
_<
<
:
¬C
OBDD
<
_<
<
:
∧BC
OBDD
<
_<
<
:
∨BC
OBDD
<
_<
<
:
CD
cSDD
T
_T
T
->
OBDD
<
_<
<
uOBDD
->
OBDD
uOBDD
<
_<
<
->
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
:
CO
FBDD
:
CT
FBDD
:
VA
OBDD
<
_<
<
:
EQ
FBDD
:
CO
FBDD
:
CT
FBDD
:
VA
OBDD
<
_<
<
:
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
:
CO
DNNF
:
FO
DNNF
:
CO
DNNF
:
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
:
CO
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
d-DNNF
:
∧BC
d-DNNF
:
CD
d-DNNF
:
SFO
DNF
:
∧BC
DNF
:
∨C
DNNF
:
∧BC
DNNF
:
∨C
DNNF
:
CD
FBDD
:
¬C
FBDD
:
CD
FBDD
:
SFO
IP
:
¬C
IP
:
∧BC
IP
:
∧C
IP
:
∨BC
IP
:
CD
IP
:
SFO
MODS
:
¬C
MODS
:
∧BC
MODS
:
∧C
MODS
:
∨BC
MODS
:
FO
NNF
:
¬C
NNF
:
∧C
NNF
:
CD
OBDD
:
¬C
OBDD
:
∧BC
OBDD
:
CD
OBDD
:
SFO
PI
:
¬C
PI
:
∧BC
PI
:
∨BC
PI
:
∨C
PI
:
CD
PI
:
FO
CNF
->
NNF
CNF
->
PI
d-DNNF
->
DNNF
d-DNNF
->
MODS
dec-SDNNF
->
OBDD
dec-SDNNF
T
_T
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
->
OBDD
<
_<
<
OBDD
<
_<
<
->
CNF
OBDD
<
_<
<
->
DNF
OBDD
<
_<
<
->
OBDD
PI
->
CNF
PI
->
DNF
PI
->
FBDD
PI
->
MODS
CNF
:
CO
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
d-DNNF
:
∧BC
d-DNNF
:
CD
d-DNNF
:
SFO
DNF
:
∧BC
DNF
:
∨C
DNNF
:
∧BC
DNNF
:
∨C
DNNF
:
CD
FBDD
:
¬C
FBDD
:
CD
FBDD
:
SFO
IP
:
¬C
IP
:
∧BC
IP
:
∧C
IP
:
∨BC
IP
:
CD
IP
:
SFO
MODS
:
¬C
MODS
:
∧BC
MODS
:
∧C
MODS
:
∨BC
MODS
:
FO
NNF
:
¬C
NNF
:
∧C
NNF
:
CD
OBDD
:
¬C
OBDD
:
∧BC
OBDD
:
CD
OBDD
:
SFO
PI
:
¬C
PI
:
∧BC
PI
:
∨BC
PI
:
∨C
PI
:
CD
PI
:
FO
CNF
->
NNF
CNF
->
PI
d-DNNF
->
DNNF
d-DNNF
->
MODS
dec-SDNNF
->
OBDD
dec-SDNNF
T
_T
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
->
OBDD
<
_<
<
OBDD
<
_<
<
->
CNF
OBDD
<
_<
<
->
DNF
OBDD
<
_<
<
->
OBDD
PI
->
CNF
PI
->
DNF
PI
->
FBDD
PI
->
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
:
¬C
SDD
:
CD
SDD
T
_T
T
:
¬C
SDD
T
_T
T
:
∧BC
SDD
T
_T
T
:
∨BC
SDD
T
_T
T
:
CD
cSDD
T
_T
T
->
cSDD
OBDD
->
cSDD
OBDD
<
_<
<
->
cSDD
T
_T
T
SDD
T
_T
T
->
SDD
SDD
:
¬C
SDD
:
CD
SDD
T
_T
T
:
¬C
SDD
T
_T
T
:
∧BC
SDD
T
_T
T
:
∨BC
SDD
T
_T
T
:
CD
cSDD
T
_T
T
->
cSDD
OBDD
->
cSDD
OBDD
<
_<
<
->
cSDD
T
_T
T
SDD
T
_T
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
:
CO
FBDD
:
CT
FBDD
:
VA
FBDD
->
OBDD
FBDD
:
CO
FBDD
:
CT
FBDD
:
VA
FBDD
->
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
:
EQ
OBDD
:
SE
OBDD
<
_<
<
:
EQ
OBDD
:
EQ
OBDD
:
SE
OBDD
<
_<
<
:
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
->
FBDD
dec-SDNNF
->
OBDD
dec-SDNNF
T
_T
T
->
dec-SDNNF
dec-SDNNF
T
_T
T
->
nFBDD
dec-SDNNF
T
_T
T
->
OBDD
<
_<
<
dec-DNNF
->
FBDD
dec-SDNNF
->
OBDD
dec-SDNNF
T
_T
T
->
dec-SDNNF
dec-SDNNF
T
_T
T
->
nFBDD
dec-SDNNF
T
_T
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
:
CD
d-SDNNF
:
FO
d-SDNNF
T
_T
T
:
∧BC
d-SDNNF
T
_T
T
:
CD
d-SDNNF
T
_T
T
:
FO
SDNNF
:
CD
SDNNF
:
FO
SDNNF
T
_T
T
:
∧BC
SDNNF
T
_T
T
:
∨C
SDNNF
T
_T
T
:
CD
SDNNF
T
_T
T
:
FO
d-SDNNF
->
uOBDD
d-SDNNF
T
_T
T
->
d-SDNNF
DNNF
->
nFBDD
SDNNF
->
nOBDD
SDNNF
T
_T
T
->
SDNNF
d-SDNNF
:
CD
d-SDNNF
:
FO
d-SDNNF
T
_T
T
:
∧BC
d-SDNNF
T
_T
T
:
CD
d-SDNNF
T
_T
T
:
FO
SDNNF
:
CD
SDNNF
:
FO
SDNNF
T
_T
T
:
∧BC
SDNNF
T
_T
T
:
∨C
SDNNF
T
_T
T
:
CD
SDNNF
T
_T
T
:
FO
d-SDNNF
->
uOBDD
d-SDNNF
T
_T
T
->
d-SDNNF
DNNF
->
nFBDD
SDNNF
->
nOBDD
SDNNF
T
_T
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
_T
T
:
¬C
cSDD
T
_T
T
:
∧BC
cSDD
T
_T
T
:
CD
cSDD
T
_T
T
:
SFO
cSDD
->
SDD
cSDD
T
_T
T
->
SDD
T
_T
T
SDD
->
d-SDNNF
SDD
T
_T
T
->
d-SDNNF
T
_T
T
cSDD
T
_T
T
:
¬C
cSDD
T
_T
T
:
∧BC
cSDD
T
_T
T
:
CD
cSDD
T
_T
T
:
SFO
cSDD
->
SDD
cSDD
T
_T
T
->
SDD
T
_T
T
SDD
->
d-SDNNF
SDD
T
_T
T
->
d-SDNNF
T
_T
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
:
¬C
d-SDNNF
->
SDD
d-SDNNF
T
_T
T
->
SDD
T
_T
T
d-SDNNF
:
¬C
d-SDNNF
->
SDD
d-SDNNF
T
_T
T
->
SDD
T
_T
T
+
bib
[41]
1987
I. Wegener, "The Complexity of Boolean Functions", 1987.
Wegener_1987
IP
->
FBDD
MODS
->
IP
PI
->
FBDD
IP
->
FBDD
MODS
->
IP
PI
->
FBDD
+
bib
[42]
2000
I. Wegener, "Branching Programs and Binary Decision Diagrams: Theory and Applications", 2000.
Wegener_2000
cSDD
T
_T
T
->
OBDD
<
_<
<
d-SDNNF
->
uOBDD
d-SDNNF
T
_T
T
->
nFBDD
d-SDNNF
T
_T
T
->
uOBDD
<
_<
<
DNF
->
nOBDD
<
_<
<
DNNF
->
nFBDD
nOBDD
<
_<
<
->
nOBDD
OBDD
<
_<
<
->
uOBDD
<
_<
<
SDNNF
->
nOBDD
SDNNF
T
_T
T
->
nOBDD
<
_<
<
uFBDD
->
FBDD
uOBDD
->
OBDD
uOBDD
<
_<
<
->
nOBDD
<
_<
<
uOBDD
<
_<
<
->
OBDD
<
_<
<
uOBDD
<
_<
<
->
uOBDD
cSDD
T
_T
T
->
OBDD
<
_<
<
d-SDNNF
->
uOBDD
d-SDNNF
T
_T
T
->
nFBDD
d-SDNNF
T
_T
T
->
uOBDD
<
_<
<
DNF
->
nOBDD
<
_<
<
DNNF
->
nFBDD
nOBDD
<
_<
<
->
nOBDD
OBDD
<
_<
<
->
uOBDD
<
_<
<
SDNNF
->
nOBDD
SDNNF
T
_T
T
->
nOBDD
<
_<
<
uFBDD
->
FBDD
uOBDD
->
OBDD
uOBDD
<
_<
<
->
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