Reversible k-valued logic circuits are finitely generated for odd k

2016/04/06 by Peter Selinger, Selinger, Peter
Computer Science · Mathematics · Physics and Astronomy · #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Quantum Physics (quant-ph) #Rings and Algebras (math.RA) #cs.ET #math.RA #quant-ph

paper · pdf · doi:10.48550/arxiv.1604.01646

3 pages

arxiv created 2016/04/06 · arxiv updated 2016/04/07

Abstract

In his 2003 paper "Towards an algebraic theory of Boolean circuits", Lafont notes that the class of reversible circuits over a set of k truth values is finitely generated when k is odd. He cites a private communication for the proof. The purpose of this short note is to make the content of that communication available.

Related

• Generating reversible circuits from higher-order functional programs
• The Classification of Reversible Bit Operations
• Finite generating sets for reversible gate sets under general conservation laws
• Strongly Universal Reversible Gate Sets
• Logic circuits from zero forcing