Feedback, trace and fixed-point semantics

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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2002)

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

Abstract

top
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.

How to cite

top

Katis, P., Sabadini, Nicoletta, and Walters, Robert F. C.. "Feedback, trace and fixed-point semantics." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 36.2 (2002): 181-194. <http://eudml.org/doc/245888>.

@article{Katis2002,
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 - Informatique Théorique et Applications},
keywords = {category with feedback-with-delay; traced monoidal category},
language = {eng},
number = {2},
pages = {181-194},
publisher = {EDP-Sciences},
title = {Feedback, trace and fixed-point semantics},
url = {http://eudml.org/doc/245888},
volume = {36},
year = {2002},
}

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 - Informatique Théorique et Applications
PY - 2002
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/245888
ER -

References

top
  1. [1] 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 
  2. [2] M. Bartha, An algebraic model of synchronous systems. Inform. and Comput. 97 (1992) 97-131. Zbl0768.68098MR1154208
  3. [3] L. Bernatsky and Z. Ésik, Sematics of flowchart programs and the free Conway theories. RAIRO: Theoret. Informatics Applic. 32 (1998) 35-78. MR1657511
  4. [4] S.L. Bloom and Z. Ésik, Axiomatising schemes and their behaviours. J. Comput. System Sci. 31 (1985) 375-393. Zbl0613.68013MR835132
  5. [5] S.L. Bloom and Z. Ésik, Iteration Theories: The Equational Logic of Iterative Processes. Springer-Verlag, EATCS Monogr. Theoret. Comput. Sci. (1993). Zbl0773.03033MR1295433
  6. [6] S.L. Bloom and Z. Ésik, Matrix and matricial iteration theories, Part I. J. Comput. System Sci. 46 (1993) 381-408. Zbl0791.08006MR1228813
  7. [7] S.L. Bloom, N. Sabadini and R.F.C. Walters, Matrices, machines and behaviors. Appl. Categorical Structures 4 (1996) 343-360. Zbl0859.18005MR1421175
  8. [8] R.F. Blute, J.R.B. Cockett and R.A.G. Seely, Feedback for linearly distributive categories: Traces and fixpoints. J. Pure Appl. Algebra 154 (2000) 27-69. Zbl0964.03063MR1787590
  9. [9] A. Carboni and R.F.C. Walters, Cartesian Bicategories I. J. Pure Appl. Algebra 49 (1987) 11-32. Zbl0637.18003MR920513
  10. [10] J. Conway, Regular Algebra and Finite Machines. Chapman and Hall, London (1971). Zbl0231.94041
  11. [11] 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.02040MR413584
  12. [12] C.C. Elgot, Matricial Theories. J. Algebra 42 (1976) 391-421. Zbl0361.18004MR430017
  13. [13] 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
  14. [14] M. Hasegawa, Models of Sharing Graphs: A categorical semantics of let and letrec, Ph.D. Thesis. Edinburgh (1997), Springer (1999). Zbl0943.68109MR1696494
  15. [15] A. Joyal, R. Street and D. Verity, Traced monoidal categories. Math. Proc. Camb. Phil. Soc. 119 (1996) 447-468. Zbl0845.18005MR1357057
  16. [16] A. Joyal and R. Street, Braided tensor categories. Adv. in Math. 102 (1993) 20-78. Zbl0817.18007MR1250465
  17. [17] W. Khalil and R.F.C. Walters, An imperative language based on distributive categories II. RAIRO: Theoret. Informatics Appl. 27 (1993) 503-522. Zbl0806.18006MR1258750
  18. [18] P. Katis, N. Sabadini and R.F.C. Walters, Bicategories of processes. J. Pure Appl. Algebra 115 (1997) 141-178. Zbl0933.18008MR1431159
  19. [19] 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
  20. [20] 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.94051MR1785817
  21. [21] 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. 
  22. [22] P. Katis, N. Sabadini and R.F.C. Walters, Recursion and concurrency, Invited talk, FICS 2001. Florence (2001). 
  23. [23] P. Katis and R.F.C. Walters, The compact closed bicategory of left adjoints. Math. Proc. Camb. Phil. Soc. 130 (2001) 77-87. Zbl0980.18002MR1797732
  24. [24] G.M. Kelly and M. Laplaza, Coherence for compact closed categories. J. Pure Appl. Algebra 19 (1980) 193-213. Zbl0447.18005MR593254
  25. [25] 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.01002MR188316
  26. [26] M. Nagata, Local rings. Interscience (1962). Zbl0123.03402MR155856
  27. [27] R. Penrose, Applications of negative dimensional torsors, edited by D.J.A. Welsh. Academic Press, New York, Comb. Math. Appl. (1971) 221-244. Zbl0216.43502MR281657
  28. [28] W.J. Rugh, Linear System Theory, Second Edition. Prentice Hall (1996). Zbl0892.93002MR1211190
  29. [29] 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. MR1375710
  30. [30] N. Sabadini, S. Vigna and R.F.C. Walters, A note on recursive functions. Math. Struct. Comput. Sci. 6 (1996) 127-139. Zbl0844.03025MR1386615
  31. [31] M.W. Shields, An introduction to Automata Theory. Blackwell Scientic Publications, Oxford (1987). 
  32. [32] A. Simpson and G. Plotkin, Complete axioms for categorical fixed-point operators, in Proc. 15th LICS (2000) 30-41. MR1946083
  33. [33] Gh. Stefanescu, On flowchart theories I: The deterministic case. J. Comput. System Sci. 35 (1985) 163-191. Zbl0628.68018MR910211
  34. [34] G. Stefanescu, Network Algebra. Springer-Verlag (2000). Zbl0956.68002MR1753209
  35. [35] R.F.C. Walters, Categories and Computer Science. Carslaw Publications (1991), Cambridge University Press (1992). Zbl0789.18001MR1204658

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.