A Canonical Algebra of Open Transition Systems

Last updated Feb 3, 2024

feedback-drawings

Abstract. Feedback and state are closely interrelated concepts. Categories with feedback, originally proposed by Katis, Sabadini and Walters, are a weakening of the notion of traced monoidal categories, with several pertinent applications in computer science. The construction of the free such categories has appeared in several different contexts, and can be considered as state bootstrapping. We show that a categorical algebra for open transition systems, Span(Graph)∗, also due to Katis, Sabadini and Walters, is the free category with feedback over Span(Set). Intuitively, this algebra of transition systems is obtained by adding state to an algebra of predicates, and therefore Span(Graph)∗ is, in this sense, the canonical such algebra.

# How to cite

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
@inproceedings{openTransitionSystems21,
  author    = {Elena Di Lavore and
               Alessandro Gianola and
               Mario Rom{\'{a}}n and
               Nicoletta Sabadini and
               Pawel Sobocinski},
  editor    = {Gwen Sala{\"{u}}n and
               Anton Wijs},
  title     = {A Canonical Algebra of Open Transition Systems},
  booktitle = {Formal Aspects of Component Software - 17th International Conference,
               {FACS} 2021, Virtual Event, October 28-29, 2021, Proceedings},
  series    = {Lecture Notes in Computer Science},
  volume    = {13077},
  pages     = {63--81},
  publisher = {Springer},
  year      = {2021},
  url       = {https://doi.org/10.1007/978-3-030-90636-8\_4},
  doi       = {10.1007/978-3-030-90636-8\_4},
  timestamp = {Sat, 25 Dec 2021 15:52:32 +0100},
  biburl    = {https://dblp.org/rec/conf/facs2/LavoreGRS021.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}