# Feedback, trace and fixed-point semantics

P. Katis; Nicoletta Sabadini; Robert F.C. Walters

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 36, Issue: 2, page 181-194
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topKatis, P., Sabadini, Nicoletta, and Walters, Robert F.C.. "Feedback, trace and fixed-point semantics." RAIRO - Theoretical Informatics and Applications 36.2 (2010): 181-194. <http://eudml.org/doc/92696>.

@article{Katis2010,

abstract = {
We introduce a notion of category with feedback-with-delay, closely related
to the notion of traced monoidal category, and show that the Circ
construction of [15] is the free category with feedback on a symmetric
monoidal category. Combining with the Int construction of
Joyal et al. [12] we obtain a description of the free compact closed
category on a symmetric monoidal category. We thus obtain a categorical
analogue of the classical localization of a ring with respect to a
multiplicative subset. In this context we define a notion of fixed-point
semantics of a category with feedback which is seen to include a variety of
classical semantics in computer science.
},

author = {Katis, P., Sabadini, Nicoletta, Walters, Robert F.C.},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {category with feedback-with-delay; traced monoidal category},

language = {eng},

month = {3},

number = {2},

pages = {181-194},

publisher = {EDP Sciences},

title = {Feedback, trace and fixed-point semantics},

url = {http://eudml.org/doc/92696},

volume = {36},

year = {2010},

}

TY - JOUR

AU - Katis, P.

AU - Sabadini, Nicoletta

AU - Walters, Robert F.C.

TI - Feedback, trace and fixed-point semantics

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 36

IS - 2

SP - 181

EP - 194

AB -
We introduce a notion of category with feedback-with-delay, closely related
to the notion of traced monoidal category, and show that the Circ
construction of [15] is the free category with feedback on a symmetric
monoidal category. Combining with the Int construction of
Joyal et al. [12] we obtain a description of the free compact closed
category on a symmetric monoidal category. We thus obtain a categorical
analogue of the classical localization of a ring with respect to a
multiplicative subset. In this context we define a notion of fixed-point
semantics of a category with feedback which is seen to include a variety of
classical semantics in computer science.

LA - eng

KW - category with feedback-with-delay; traced monoidal category

UR - http://eudml.org/doc/92696

ER -

## References

top- S. Abramsky, Retracing some paths in process algebras, Concur '96, edited by U. Montanari and V. Sassone. Springer-Verlag, Lecture Notes in Comput. Sci. 1119 (1996) 1-17
- M. Bartha, An algebraic model of synchronous systems. Inform. and Comput.97 (1992) 97-131. Zbl0768.68098
- L. Bernatsky and Z. Ésik, Sematics of flowchart programs and the free Conway theories. RAIRO: Theoret. Informatics Applic.32 (1998) 35-78.
- S.L. Bloom and Z. Ésik, Axiomatising schemes and their behaviours. J. Comput. System Sci.31 (1985) 375-393. Zbl0613.68013
- S.L. Bloom and Z. Ésik, Iteration Theories: The Equational Logic of Iterative Processes. Springer-Verlag, EATCS Monogr. Theoret. Comput. Sci. (1993). Zbl0773.03033
- S.L. Bloom and Z. Ésik, Matrix and matricial iteration theories, Part I. J. Comput. System Sci.46 (1993) 381-408. Zbl0791.08006
- S.L. Bloom, N. Sabadini and R.F.C. Walters, Matrices, machines and behaviors. Appl. Categorical Structures4 (1996) 343-360. Zbl0859.18005
- R.F. Blute, J.R.B. Cockett and R.A.G. Seely, Feedback for linearly distributive categories: Traces and fixpoints. J. Pure Appl. Algebra154 (2000) 27-69. Zbl0964.03063
- A. Carboni and R.F.C. Walters, Cartesian Bicategories I. J. Pure Appl. Algebra49 (1987) 11-32. Zbl0637.18003
- J. Conway, Regular Algebra and Finite Machines. Chapman and Hall, London (1971). Zbl0231.94041
- C.C. Elgot, Monadic computation and iterative algebraic theories, edited by J.C. Shepherdson. North Holland, Amsterdam, Logic Colloquium 1973, Studies in Logic 80 (1975). Zbl0327.02040
- C.C. Elgot, Matricial Theories. J. Algebra42 (1976) 391-421.
- F. Gadducci, U. Montanari, P. Katis, N. Sabadini and R.F.C. Walters, Comparing Cospan-spans and Tiles via a Hoare-style process calculus. TOSCA Udine, Electron. Notes Theoret. Comput. Sci. 62 (2001) 152-171. Zbl1268.68126
- M. Hasegawa, Models of Sharing Graphs: A categorical semantics of let and letrec,Ph.D. Thesis. Edinburgh (1997), Springer (1999). Zbl0943.68109
- A. Joyal, R. Street and D. Verity, Traced monoidal categories. Math. Proc. Camb. Phil. Soc.119 (1996) 447-468. Zbl0845.18005
- A. Joyal and R. Street, Braided tensor categories. Adv. in Math.102 (1993) 20-78. Zbl0817.18007
- W. Khalil and R.F.C. Walters, An imperative language based on distributive categories II. RAIRO: Theoret. Informatics Appl.27 (1993) 503-522. Zbl0806.18006
- P. Katis, N. Sabadini and R.F.C. Walters, Bicategories of processes. J. Pure Appl. Algebra115 (1997) 141-178. Zbl0933.18008
- P. Katis, N. Sabadini and R.F.C. Walters, Span(Graph): A categorical algebra of transition systems, in Proc. Algebraic Methodology and Software Technology. Springer-Verlag, Lecture Notes in Comput. Sci. 1349 (1997) 307-321. Zbl0885.18004
- P. Katis, N. Sabadini and R.F.C. Walters, On the algebra of systems with feedback and boundary. Rend. Circ. Mat. Palermo (2) Suppl.63 (2000) 123-156. Zbl1003.94051
- P. Katis, N. Sabadini and R.F.C. Walters, A formalization of the IWIM Model, in Proc. COORDINATION 2000, edited by A. Porto and G.-C. Roman. Springer-Verlag, Lecture Notes in Comput. Sci. 1906 (2000) 267-283.
- P. Katis, N. Sabadini and R.F.C. Walters, Recursion and concurrency, Invited talk, FICS 2001. Florence (2001).
- P. Katis and R.F.C. Walters, The compact closed bicategory of left adjoints. Math. Proc. Camb. Phil. Soc.130 (2001) 77-87. Zbl0980.18002
- G.M. Kelly and M. Laplaza, Coherence for compact closed categories. J. Pure Appl. Algebra19 (1980) 193-213. Zbl0447.18005
- K. Krohn and J. Rhodes, Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines. Trans. Amer. Math. Soc.116 (1965) 450-464. Zbl0148.01002
- M. Nagata, Local rings. Interscience (1962). Zbl0123.03402
- R. Penrose, Applications of negative dimensional torsors, edited by D.J.A. Welsh. Academic Press, New York, Comb. Math. Appl. (1971) 221-244.
- W.J. Rugh, Linear System Theory, Second Edition. Prentice Hall (1996). Zbl0892.93002
- J.J.M.M. Rutten, A calculus of transition systems (towards universal coalgebra), in Modal Logic and Process Algebra, a bisimulation perspective, edited by A. Ponse, M. de Rijke and Y. Venema. CSLI Publications, Standford, CSLI Lecture Notes 53 (1995) 231-256.
- N. Sabadini, S. Vigna and R.F.C. Walters, A note on recursive functions. Math. Struct. Comput. Sci.6 (1996) 127-139. Zbl0844.03025
- M.W. Shields, An introduction to Automata Theory. Blackwell Scientic Publications, Oxford (1987).
- A. Simpson and G. Plotkin, Complete axioms for categorical fixed-point operators, in Proc. 15th LICS (2000) 30-41.
- Gh. Stefanescu, On flowchart theories I: The deterministic case. J. Comput. System Sci.35 (1985) 163-191. Zbl0628.68018
- G. Stefanescu, Network Algebra. Springer-Verlag (2000).
- R.F.C. Walters, Categories and Computer Science. Carslaw Publications (1991), Cambridge University Press (1992). Zbl0789.18001

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.