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.CALCO.2017.2
URN: urn:nbn:de:0030-drops-80535
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8053/
Go to the corresponding LIPIcs Volume Portal

Gianola, Alessandro ; Kasangian, Stefano ; Sabadini, Nicoletta

Cospan/Span(Graph): an Algebra for Open, Reconfigurable Automata Networks

pdf-format:
LIPIcs-CALCO-2017-2.pdf (0.9 MB)

Abstract

Span(Graph) was introduced by Katis, Sabadini and Walters as a categorical algebra of automata with interfaces, with main operation being communicating-parallel composition. Additional operations provide also a calculus of connectors or wires among components.
A system so described has two aspects: an informal network geometry arising from the algebraic expression, and a space of states and transition given by its evaluation in Span(Graph). So, Span(Graph) yields purely compositional, hierarchical descriptions of networks with a fixed topology .
The dual algebra Cospan(Graph) allows to describe also the sequential behaviour of systems. Both algebras, of spans and of cospans, are symmetrical monoidal categories with commutative separable algebra structures on the objects.
Hence, the combined algebra CospanSpan(Graph) can be interpreted as a general algebra for reconfigurable/hierarchical networks, generalizing the usual Kleene's algebra for classical automata. We present some examples of systems described in this setting.

BibTeX - Entry

@InProceedings{gianola_et_al:LIPIcs:2017:8053,
  author =	{Alessandro Gianola and Stefano Kasangian and Nicoletta Sabadini},
  title =	{{Cospan/Span(Graph): an Algebra for Open, Reconfigurable Automata Networks}},
  booktitle =	{7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-033-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{72},
  editor =	{Filippo Bonchi and Barbara K{\"o}nig},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8053},
  URN =		{urn:nbn:de:0030-drops-80535},
  doi =		{10.4230/LIPIcs.CALCO.2017.2},
  annote =	{Keywords: Categories, Automata, Composition, Networks}
}

Keywords: Categories, Automata, Composition, Networks
Collection: 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)
Issue Date: 2017
Date of publication: 17.11.2017

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