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.  
  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.  
  5. S.L. Bloom and Z. Ésik, Iteration Theories: The Equational Logic of Iterative Processes. Springer-Verlag, EATCS Monogr. Theoret. Comput. Sci. (1993).  
  6. S.L. Bloom and Z. Ésik, Matrix and matricial iteration theories, Part I. J. Comput. System Sci.46 (1993) 381-408.  
  7. S.L. Bloom, N. Sabadini and R.F.C. Walters, Matrices, machines and behaviors. Appl. Categorical Structures4 (1996) 343-360.  
  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.  
  9. A. Carboni and R.F.C. Walters, Cartesian Bicategories I. J. Pure Appl. Algebra49 (1987) 11-32.  
  10. J. Conway, Regular Algebra and Finite Machines. Chapman and Hall, London (1971).  
  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).  
  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.  
  14. M. Hasegawa, Models of Sharing Graphs: A categorical semantics of let and letrec,Ph.D. Thesis. Edinburgh (1997), Springer (1999).  
  15. A. Joyal, R. Street and D. Verity, Traced monoidal categories. Math. Proc. Camb. Phil. Soc.119 (1996) 447-468.  
  16. A. Joyal and R. Street, Braided tensor categories. Adv. in Math.102 (1993) 20-78.  
  17. W. Khalil and R.F.C. Walters, An imperative language based on distributive categories II. RAIRO: Theoret. Informatics Appl.27 (1993) 503-522.  
  18. P. Katis, N. Sabadini and R.F.C. Walters, Bicategories of processes. J. Pure Appl. Algebra115 (1997) 141-178.  
  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.  
  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.  
  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.  
  24. G.M. Kelly and M. Laplaza, Coherence for compact closed categories. J. Pure Appl. Algebra19 (1980) 193-213.  
  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.  
  26. M. Nagata, Local rings. Interscience (1962).  
  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).  
  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.  
  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.  
  34. G. Stefanescu, Network Algebra. Springer-Verlag (2000).  
  35. R.F.C. Walters, Categories and Computer Science. Carslaw Publications (1991), Cambridge University Press (1992).  

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.