×

On the geometry and algebra of networks with state. (English) Zbl 1359.68226

Summary: In [P. Katis et al., Lect. Notes Comput. Sci. 1349, 307–321 (1997; Zbl 0885.18004)] an algebra of automata with interfaces, \(\mathbf{Span}(\mathbf{Graph})\), was introduced with main operation being communicating-parallel composition – a system is represented by an expression in this algebra. 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 \(\mathbf{Span}(\mathbf{Graph})\). Note that \(\mathbf{Span}(\mathbf{Graph})\) yields purely compositional descriptions of systems.
In this paper we give an alternative globally (non-compositional) view of the same systems. In order to do this we make mathematically precise the network geometry in terms of monoidal graphs, and assignment of state in terms of morphisms of monoidal graphs. We call such globally described systems networks with state. To relate networks with state and \(\mathbf{Span}(\mathbf{Graph})\) systems we use the algebra of cospans of monoidal graphs.
As an illustration we give a new representation of a (non-compositionally described) class of Petri nets in the compositional setting of \(\mathbf{Span}(\mathbf{Graph})\). We also present a tool for calculating with networks with state.
Both algebras, of spans and of cospans, are symmetric monoidal categories with commutative separable algebra structures on the objects.
We include a short section, following [R. Rosebrugh et al., Theory Appl. Categ. 26, 743–767 (2012; Zbl 1275.18008)], in which we show that a simple modification of the algebra allows the description of networks in which the tangling of connectors may be represented, yielding a connection with the theory of knots.

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
18D10 Monoidal, symmetric monoidal and braided categories (MSC2010)

Software:

WiCcA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Katis, P.; Sabadini, N.; Walters, R., Span(graph): a categorical algebra of transition systems, 1349, 307-321 (1997) · Zbl 0885.18004
[2] Rosebrugh, R.; Sabadini, N.; Walters, R., Tangled circuits, 26, 27, 743-767 (2012) · Zbl 1275.18008
[4] Katis, P.; Sabadini, N.; Walters, R., A formalization of the IWIM model, 1906, 267-283 (2000)
[5] Selinger, P., A survey of graphical languages for monoidal categories, 813, 289-355 (2011) · Zbl 1217.18002
[6] Penrose, R., Applications of negative dimensional tensors, Combin. Math. Appl. (1971) · Zbl 0216.43502
[7] Joyal, A.; Street, R., The geometry of tensor calculus, i, Adv. Math., 88, 1, 55-112 (1991) · Zbl 0738.18005
[8] Bènabou, J., Introduction to bicategories, 47, 1-77 (1967) · Zbl 1375.18001
[9] Rosebrugh, R.; Sabadini, N.; Walters, R., Tangled circuits, 26, 27, 743-767 (2012) · Zbl 1275.18008
[10] Katis, P.; Sabadini, N.; Walters, R., On the algebra of feedback and systems with boundary, Rend. Circ. Mat. Palermo (2), 123-156 (2000) · Zbl 1003.94051
[11] Katis, P.; Sabadini, Nicoletta; Walters, Robert F. C., Feedback, trace and fixed-point semantics, RAIRO Theor. Inform. Appl., 36, 2, 181-194 (2002) · Zbl 1050.68100
[12] Rosebrugh, R.; Sabadini, N.; Walters, R., A formalization of the iwim model, 15, 6, 164-177 (2005) · Zbl 1087.18003
[13] Rosebrugh, R.; Sabadini, N.; Walters, R., Calculating colimits compositionally, (Degano, P.; De Nicola, R.; Meseguer, J., Concurrency, Graphs and Models. Concurrency, Graphs and Models, Lecture Notes in Comput. Sci., vol. 5065 (2008), Springer: Springer Berlin, Heidelberg), 581-592 · Zbl 1144.18003
[14] Carboni, A.; Walters, R., Cartesian bicategories i, J. Pure Appl. Algebra, 49, 1, 11-32 (1987) · Zbl 0637.18003
[15] Eilenberg, S., Automata, Languages and Machines, Vol. A (1972), Academic Press: Academic Press New York
[16] Bloom, S. L.; Ésik, Z., Iteration Theories: The Equational Logic of Iterative Processes (1993), Springer-Verlag New York, Inc.: Springer-Verlag New York, Inc. New York, NY, USA · Zbl 0796.68153
[17] Stefănescu, G., Network Algebra (2000), Springer-Verlag New York, Inc.: Springer-Verlag New York, Inc. Secaucus, NJ, USA · Zbl 0956.68002
[18] Kock, J., Frobenius Algebras and 2D Topological Quantum Field Theories (2004), Cambridge University Press · Zbl 1046.57001
[19] Bliudze, S.; Sifakis, J., The algebra of connectors: structuring interaction in bip (2007), 11-20
[20] Fong, B., Decorated cospans · Zbl 1351.18003
[21] Baez, J. C.; Erbele, J., Categories in control · Zbl 1316.18009
[22] Baez, J. C.; Fong, B., A compositional framework for passive linear networks · Zbl 1402.18005
[23] Meseguer, J.; Montanari, U., Petri nets are monoids, Inform. and Comput., 88, 2, 105-155 (1990) · Zbl 0711.68077
[24] Albasini, L.d. F.; Sabadini, N.; Walters, R. F.C., The compositional construction of Markov processes · Zbl 1216.18005
[25] Albasini, L.d. F.; Sabadini, N.; Walters, R. F.C., The compositional construction of Markov processes II · Zbl 1216.18005
[26] Gadducci, F.; Heckel, R.; Llabrés, M., A bi-categorical axiomatisation of concurrent graph rewriting, (Conference on Category Theory and Computer Science. Conference on Category Theory and Computer Science, {CTCS} ’99. Conference on Category Theory and Computer Science. Conference on Category Theory and Computer Science, {CTCS} ’99, Electron. Notes Theor. Comput. Sci., vol. 29 (1999)), 80-100 · Zbl 0967.68089
[27] Bruni, R.; Melgratti, H.; Montanari, U.; Sobocinski, P., Connector algebras for C/E and P/T nets’ interactions · Zbl 1274.68224
[28] Sobociński, P., Representations of petri net interactions, 6269, 554-568 (2010) · Zbl 1287.68142
[29] Lantair, J.; Sobociński Wicca, P., Lts generation tool for wire calculus, 6859, 407-412 (2011) · Zbl 1344.68169
[30] Schiavio, F., SpanTools program (2012)
[31] Freyd, P. J.; Yetter, D. N., Braided compact closed categories with applications to low dimensional topology, Adv. Math., 77, 2, 156-182 (1989) · Zbl 0679.57003
[32] Yetter, D., Functorial Knot Theory: Categories of Tangles, Coherence, Categorical Deformations, and Topological Invariants, Ser. Knots Everything (2001), World Scientific · Zbl 0977.57005
[33] Joyal, A.; Street, R., Braided monoidal categories, Adv. Math., 102, 1, 20-78 (1993) · Zbl 0817.18007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.