A sound and complete denotational, operational, and algebraic semantics for synchronous sequential circuits with arbitrary feedback, plus a hypergraph rewriting framework for digital circuits.
A Finite Axiomatisation of Finite-State Automata Using String Diagrams
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We develop a fully diagrammatic approach to finite-state automata, based on reinterpreting their usual state-transition graphical representation as a two-dimensional syntax of string diagrams. In this setting, we are able to provide a complete equational theory for language equivalence, with two notable features. First, the proposed axiomatisation is finite. Second, the Kleene star is a derived concept, as it can be decomposed into more primitive algebraic blocks.
fields
cs.LO 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Foundations of Digital Circuits: Denotation, Operational, and Algebraic Semantics
A sound and complete denotational, operational, and algebraic semantics for synchronous sequential circuits with arbitrary feedback, plus a hypergraph rewriting framework for digital circuits.