Institut
de Mathématiques de Luminy

Abstract 2002-30 |

**Lafont** Yves.

Towards an algebraic theory of Boolean circuits

Following the ideas of Burroni, we consider logical gates as generators for some algebraic structure with two compositions, and we are interested in the rel ations satisfied by those generators. For that purpose, we introduce canonical forms and rewriting systems. Up to now, we have mainly studied the basic case and the linear case, but we hope that our methods can be used to get presentations by generators and relations for the (reversible) classical case and for the (unitary) quantum case. Keywords: boolean circuit; reversible gate; monoidal category; presentation by generators and relations; canonical form; rewriting; symmetric group; alternating group; linear group; orthogonal group. |