License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2017.24
URN: urn:nbn:de:0030-drops-76715
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7671/
Go to the corresponding LIPIcs Volume Portal

Ghica, Dan R. ; Jung, Achim ; Lopez, Aliaume

Diagrammatic Semantics for Digital Circuits

pdf-format:
LIPIcs-CSL-2017-24.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{ghica_et_al:LIPIcs:2017:7671,
  author =	{Dan R. Ghica and Achim Jung and Aliaume Lopez},
  title =	{{Diagrammatic Semantics for Digital Circuits}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Valentin Goranko and Mads Dam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7671},
  URN =		{urn:nbn:de:0030-drops-76715},
  doi =		{10.4230/LIPIcs.CSL.2017.24},
  annote =	{Keywords: digital circuits, monoidal categories, string diagrams, rewriting, operational semantics}
}

Keywords: digital circuits, monoidal categories, string diagrams, rewriting, operational semantics
Collection: 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
Issue Date: 2017
Date of publication: 16.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI