On equational classes of Boolean functions
by
Stephan Földes
Tampere University of Technology, Finland
Coauthors: Miguel Couceiro (Tampere U of Technology and U of Tampere, Finland), Oya Ekin (Bilkent, Ankara), Peter L. Hammer (Rutgers, New Jersey), Lisa Hellerstein (Polytechnic University, New York), Grant Pogosyan (International Christian University, Tokyo)

Certain classes of Boolean functions, including all Post classes, can be characterized by functional equations. Recent work by this group of authors and by Pippenger has addressed issues such as necessary and sufficient conditions for such characterizations to exist, connections with preservation of relations, connection with the HSP Theorem, minimum number of equations / variables required, and constraints on the form of the equations allowed. Published and current results related to these issues will be discussed.

Date received: July 10, 2002

Copyright © 2002 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caiv-49.