Multi-level logic with constant depth: recent research from Italy

(joint work by Anna Bernasconi, Valentina Ciriani, Roberto Cordone,

Fabrizio Luccio, Linda Pagli, Tiziano Villa)

In this talk we survey recent research on logic representations

with 3 and 4 levels, which trade-off optimality vs. computing time,

exploring algebraic forms between classical sum-of-products and the

still largely unchartered domain of unrestricted multi-level logic.

In particular we present:

EXOR-Sum-of-Products (EXOR-SOP or SPP) forms and bounded-fanin SPPs;

EXOR-Projected Sum-of-Products (EP-SOP), consisting in a four level

network;

Projected Sum-of-Products (P-SOP), based on projections of minimal

SOP forms onto generic subsets of the Boolean space.

Available exact and heuristic minimization algorithms will be mentioned,

together with complexity results.