Computational methods in discrete mathematics

On the effective representation of disjunctive normal forms by diagrams of a special kind

A. A. Semenov

Institute of System Dynamics and Control Theory, Siberian Branch of the Russian Academy of Sciences, Irkutsk

Abstract: 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.

UDC: 519.7