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

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 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
  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. M. Bartha, An algebraic model of synchronous systems. Inform. and Comput.97 (1992) 97-131.  Zbl0768.68098
  3. L. Bernatsky and Z. Ésik, Sematics of flowchart programs and the free Conway theories. RAIRO: Theoret. Informatics Applic.32 (1998) 35-78.  
  4. S.L. Bloom and Z. Ésik, Axiomatising schemes and their behaviours. J. Comput. System Sci.31 (1985) 375-393.  Zbl0613.68013
  5. S.L. Bloom and Z. Ésik, Iteration Theories: The Equational Logic of Iterative Processes. Springer-Verlag, EATCS Monogr. Theoret. Comput. Sci. (1993).  Zbl0773.03033
  6. S.L. Bloom and Z. Ésik, Matrix and matricial iteration theories, Part I. J. Comput. System Sci.46 (1993) 381-408.  Zbl0791.08006
  7. S.L. Bloom, N. Sabadini and R.F.C. Walters, Matrices, machines and behaviors. Appl. Categorical Structures4 (1996) 343-360.  Zbl0859.18005
  8. 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
  9. A. Carboni and R.F.C. Walters, Cartesian Bicategories I. J. Pure Appl. Algebra49 (1987) 11-32.  Zbl0637.18003
  10. J. Conway, Regular Algebra and Finite Machines. Chapman and Hall, London (1971).  Zbl0231.94041
  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.02040
  12. C.C. Elgot, Matricial Theories. J. Algebra42 (1976) 391-421.  
  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. M. Hasegawa, Models of Sharing Graphs: A categorical semantics of let and letrec,Ph.D. Thesis. Edinburgh (1997), Springer (1999).  Zbl0943.68109
  15. A. Joyal, R. Street and D. Verity, Traced monoidal categories. Math. Proc. Camb. Phil. Soc.119 (1996) 447-468.  Zbl0845.18005
  16. A. Joyal and R. Street, Braided tensor categories. Adv. in Math.102 (1993) 20-78.  Zbl0817.18007
  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.18006
  18. P. Katis, N. Sabadini and R.F.C. Walters, Bicategories of processes. J. Pure Appl. Algebra115 (1997) 141-178.  Zbl0933.18008
  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. 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
  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. P. Katis, N. Sabadini and R.F.C. Walters, Recursion and concurrency, Invited talk, FICS 2001. Florence (2001).  
  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.18002
  24. G.M. Kelly and M. Laplaza, Coherence for compact closed categories. J. Pure Appl. Algebra19 (1980) 193-213.  Zbl0447.18005
  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.01002
  26. M. Nagata, Local rings. Interscience (1962).  Zbl0123.03402
  27. R. Penrose, Applications of negative dimensional torsors, edited by D.J.A. Welsh. Academic Press, New York, Comb. Math. Appl. (1971) 221-244.  
  28. W.J. Rugh, Linear System Theory, Second Edition. Prentice Hall (1996).  Zbl0892.93002
  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.  
  30. N. Sabadini, S. Vigna and R.F.C. Walters, A note on recursive functions. Math. Struct. Comput. Sci.6 (1996) 127-139.  Zbl0844.03025
  31. M.W. Shields, An introduction to Automata Theory. Blackwell Scientic Publications, Oxford (1987).  
  32. A. Simpson and G. Plotkin, Complete axioms for categorical fixed-point operators, in Proc. 15th LICS (2000) 30-41.  
  33. Gh. Stefanescu, On flowchart theories I: The deterministic case. J. Comput. System Sci.35 (1985) 163-191.  Zbl0628.68018
  34. G. Stefanescu, Network Algebra. Springer-Verlag (2000).  
  35. R.F.C. Walters, Categories and Computer Science. Carslaw Publications (1991), Cambridge University Press (1992).  Zbl0789.18001

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.