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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Compositional Control-Driven Boolean Circuits

  • Damian Arellanes

摘要

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.