Completeness for Probabilistic Boolean Tapes
This work establishes a foundational completeness result for a diagrammatic language of probabilistic programming, which is significant for researchers in categorical semantics and probabilistic programming.
The paper provides a complete set of axioms for the semantics of probabilistic Boolean circuits in terms of Markov kernels, building on completeness results for partial Boolean circuits and probabilistic Boolean tapes.
Probabilistic Boolean circuits have recently been proposed as a string-diagrammatic foundation for finite probabilistic programming. In this paper, we present a complete set of axioms for their semantics in terms of Markov kernels. Our approach is based on two intermediate results: completeness for \emph{partial} Boolean circuits and completeness for probabilistic Boolean tapes, a diagrammatic language for rig categories.