Towards an algebraic theory of Boolean circuits.
type: Item
instance of: scholarly article
title: Towards an algebraic theory of Boolean circuits.
zbMATH Open document ID: 1037.94015
DOI: 10.1016/S0022-4049(03)00069-0
author: Yves Lafont
published in: Journal of Pure and Applied Algebra
publication date: 2003-10-15T00:00:00Z
review text: Logical gates are considered as generators for an algebraic structure of circuits with sequential and parallel compositions of gates. Circuits made up of logical gates are considered as diagrams and are analyzed by using knot theory. To analyze diagrams, a canonical form and rewriting systems are introduced. A typical theorem in this work has the form: The generators \(a\), \(b\), \(c\) and the relations \(d\), \(f\), \(g\) form a presentation of the monoidal subcategory \(H\).
reviewed by: A. V. Chashkin
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 08A05
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 18D10
Mathematics Subject Classification ID: 68Q10
zbMATH DE Number: 1993284
zbMATH Keywords: Boolean circuit
zbMATH Keywords: knot theory
zbMATH Keywords: canonical form
zbMATH Keywords: rewriting system
MaRDI profile type: Publication
cites work: Higher-dimensional word problems with applications to equational logic
cites work: Q3138543
cites work: A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier)
cites work: Church-Rooser property and homology of monoids
cites work: FUNCTORIAL SEMANTICS OF ALGEBRAIC THEORIES
cites work: Q5639839
cites work: Minimality of the system of seven equations for the category of finite sets
cites work: Word problems and a homological finiteness condition for monoids
cites work: A finiteness condition for rewriting systems
description: scientific article; zbMATH DE number 1993284