Geodesic
On the effective representation of disjunctive normal forms by diagrams of a special kind
Prikladnaya Diskretnaya Matematika. Supplement, no. 6 (2013), pp. 125-129.

Voir la notice de l'article provenant de la source Math-Net.Ru

For an arbitrary disjunctive normal form of a Boolean function, a disjunctive diagram representation is proposed. This kind of diagrams is constructed in a polynomial time and can be used to reduce the size of conflict databases produced during non-chronological DPLL derivation.
Keywords: decision diagrams, BDD, ZDD, disjunctive diagrams. 
@article{PDMA_2013_6_a56,
     author = {A. A. Semenov},
     title = {On the effective representation of disjunctive normal forms by diagrams of a special kind},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {125--129},
     publisher = {mathdoc},
     number = {6},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2013_6_a56/}
}
TY  - JOUR
AU  - A. A. Semenov
TI  - On the effective representation of disjunctive normal forms by diagrams of a special kind
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2013
SP  - 125
EP  - 129
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2013_6_a56/
LA  - ru
ID  - PDMA_2013_6_a56
ER  - 
%0 Journal Article
%A A. A. Semenov
%T On the effective representation of disjunctive normal forms by diagrams of a special kind
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2013
%P 125-129
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2013_6_a56/
%G ru
%F PDMA_2013_6_a56
A. A. Semenov. On the effective representation of disjunctive normal forms by diagrams of a special kind. Prikladnaya Diskretnaya Matematika. Supplement, no. 6 (2013), pp. 125-129. http://geodesic.mathdoc.fr/item/PDMA_2013_6_a56/

[1] Bryant R. E., “Graph-based algorithms for Boolean function manipulation”, IEEE Trans. Comput., 35:8 (1986), 677–691 | DOI | Zbl

[2] Minato S., “Zero-suppressed BDDs for set manipulation in combinatorial problems”, Proc. DAC-93 (June 14–18, 1993, Dallas, Texas), 272–277

[3] Dowling W., Gallier J., “Linear-time algorithms for testing the satisfiability of propositional Horn formulae”, J. Logic Programming, 1:3 (1984), 267–284 | DOI | MR | Zbl

[4] Marques-Silva J. P., Sakallah K. A., “GRASP: A search algorithm for propositional satisfiability”, IEEE Trans. Comput., 48:5 (1999), 506–521 | DOI | MR

[5] Ignatev A. S., Semenov A. A., “Algoritmy raboty s ROBDD kak s bazami bulevykh ogranichenii”, Prikladnaya diskretnaya matematika, 2010, no. 1, 86–104 | Zbl

[6] Ignatiev A., Semenov A., “DPLL+ROBDD derivation applied to inversion of some cryptographic functions”, LNCS, 6695, 2011, 76–89 | MR | Zbl

[7] Een N., Sorensson N., “Translating pseudo-Boolean constraints into SAT”, J. Satisfiability, Boolean Modeling and Computation, 2 (2006), 1–25