Termination of Rewriting on Reversible Boolean Circuits as a Free 3-Category Problem

Abstract

Reversible Boolean Circuits are an interesting computational model under many aspects and in different fields, ranging from Reversible Computing to Quantum Computing. Our contribution is to describe a specific class of Reversible Boolean Circuits - which is as expressive as classical circuits - as a bi-dimensional diagrammatic programming language. We uniformly represent the Reversible Boolean Circuits we focus on as a free 3-category Toff. This formalism allows us to incorporate the representation of circuits and of rewriting rules on them, and to prove termination of rewriting. Termination follows from defining a non-identities-preserving functor from our free 3-category Toff into a suitable 3-category Move that traces the "moves" applied to wires inside circuits.

Presented at the 24th Italian Conference on Theoretical Computer Science (ICTCS 2023), September 13-15, 2023, Palermo, Italy