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