A Circus of Circuits: Connections Between Decision Diagrams, Circuits, and Automata

2024/04/15 by Antoine Amarilli, Amarilli, Antoine, Marcelo Arenas +9 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Machine Learning and Algorithms #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2404.09674

openalex publication_date 2024/04/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This document is an introduction to two related formalisms to define Boolean functions: binary decision diagrams, and Boolean circuits. It presents these formalisms and several of their variants studied in the setting of knowledge compilation. Last, it explains how these formalisms can be connected to the notions of automata over words and trees.

Cited by

• On approximating the f-divergence between two Ising models

Related

• Declarative Combinatorics: Boolean Functions, Circuit Synthesis and BDDs in Haskell
• On the Relative Succinctness of Sentential Decision Diagrams
• Binary Decision Diagrams are a Subset of Bayesian Nets
• A framework for (de)composing with Boolean automata networks
• Tractable Boolean and Arithmetic Circuits