Diagrammatic Semantics for Digital Circuits

Dan R Ghica, Achim Jung, Aliaume Lopez

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)
74 Downloads (Pure)

Abstract

We introduce a general diagrammatic theory of digital circuits, based on connections between monoidal categories and graph rewriting. The main achievement of the paper is conceptual, filling a foundational gap in reasoning syntactically and symbolically about a large class of digital circuits (discrete values, discrete delays, feedback). This complements the dominant approach to
circuit modelling, which relies on simulation. The main advantage of our symbolic approach is the enabling of automated reasoning about parametrised circuits, with a potentially interesting new application to partial evaluation of digital circuits. Relative to the recent interest and activity in categorical and diagrammatic methods, our work makes several new contributions. The most important is establishing that categories of digital circuits are Cartesian and admit, in the presence of feedback expressive iteration axioms. The second is producing a general yet simple graph-rewrite framework for reasoning about such categories in which the rewrite rules are computationally efficient, opening the way for practical applications.
Original languageEnglish
Title of host publication26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
EditorsValentin Goranko, Mads Dam
PublisherSchloss Dagstuhl
Pages24:1-24:16
Number of pages16
Volume82
ISBN (Electronic)978-3-95977-045-3
ISBN (Print)978-1-51084-711-8
DOIs
Publication statusPublished - 1 Sept 2017
Event26th EACSL Annual Conference on Computer Science Logic (CSL 2017) - Stockholm, Sweden
Duration: 20 Aug 201724 Aug 2017
https://www.math-stockholm.se/en/konferenser-och-akti/logic-in-stockholm-2/26th-eacsl-annual-co

Publication series

NameLeibniz International Proceedings in Informatics
PublisherSchloss Dagstuhl
Volume82

Conference

Conference26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
Abbreviated titleCSL 2017
Country/TerritorySweden
CityStockholm
Period20/08/1724/08/17
Internet address

Keywords

  • digital circuits
  • string diagrams
  • rewriting
  • operational semantics

Fingerprint

Dive into the research topics of 'Diagrammatic Semantics for Digital Circuits'. Together they form a unique fingerprint.

Cite this