RUTCOR Colloquia - June 1, 2006
Speaker: Erkko Lehtonen
Affiliation: Tampere University of Technology, Finland
Title: Composition of Post classes and normal forms of Boolean functions
Time: 1:30 - 2:30 PM
Location: RUTCOR Building - Room 139, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The class composition of Boolean clones is investigated. All pairs of
Post classes are classified according to whether their composition is
a clone (in which case it is their join in the Post lattice).
Factorizations of the clone of all Boolean functions as a composition
of minimal clones are described and seen to correspond to normal form
representations of Boolean functions. The median normal form is shown
to provide a more efficient normal form representation than the DNF,
CNF, and Zhegalkin (Reed-Muller) polynomial representations.
Joint work with Miguel Couceiro and Stephan Foldes.
Back to Seminars Page.
Back to RUTCOR homepage.
| 
