Compositional Control-Driven Boolean Circuits
This addresses a foundational problem in theoretical computer science for researchers studying circuit compositionality, though it appears incremental as it builds on existing Boolean circuit theory.
The paper tackles the theoretical gap in compositional construction of Boolean circuits by proposing colimit-based operators for sequential, parallel, branching, and iterative circuits, resulting in a new control-driven Boolean circuit model that is at least as powerful as classical Boolean circuits for computing any Boolean function on arbitrary-length inputs.
Boolean circuits abstract away from physical details to focus on the logical structure and computational behaviour of digital components. Although such circuits have been studied for many decades, compositionality has been widely ignored or examined in an informal manner, which is a property for combining circuits without delving into their internal structure, while supporting modularity and formal reasoning. In this paper, we address this longstanding theoretical gap by proposing colimit-based operators for compositional circuit construction. We define separate operators for forming sequential, parallel, branching and iterative circuits. As composites encapsulate explicit control flow, a new model of computation emerges which we refer to as (families of) control-driven Boolean circuits. We show how this model is at least as powerful as its classical counterpart. In other words, it is able to non-uniformly compute any Boolean function on inputs of arbitrary length.