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.
@article{ITA_2002__36_2_181_0,
author = {Katis, P. and Sabadini, Nicoletta and Walters, Robert F. C.},
title = {Feedback, trace and fixed-point semantics},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {181--194},
publisher = {EDP-Sciences},
volume = {36},
number = {2},
year = {2002},
doi = {10.1051/ita:2002009},
mrnumber = {1948768},
zbl = {1050.68100},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2002009/}
}
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 SP - 181 EP - 194 VL - 36 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2002009/ DO - 10.1051/ita:2002009 LA - en ID - ITA_2002__36_2_181_0 ER -
%0 Journal Article %A Katis, P. %A Sabadini, Nicoletta %A Walters, Robert F. C. %T Feedback, trace and fixed-point semantics %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2002 %P 181-194 %V 36 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2002009/ %R 10.1051/ita:2002009 %G en %F ITA_2002__36_2_181_0
Katis, P.; Sabadini, Nicoletta; Walters, Robert F. C. Feedback, trace and fixed-point semantics. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 2, pp. 181-194. doi : 10.1051/ita:2002009. http://www.numdam.org/articles/10.1051/ita:2002009/
[1] , 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] , An algebraic model of synchronous systems. Inform. and Comput. 97 (1992) 97-131. | MR | Zbl
[3] and, Sematics of flowchart programs and the free Conway theories. RAIRO: Theoret. Informatics Applic. 32 (1998) 35-78. | Numdam | MR
[4] and, Axiomatising schemes and their behaviours. J. Comput. System Sci. 31 (1985) 375-393. | MR | Zbl
[5] and, Iteration Theories: The Equational Logic of Iterative Processes. Springer-Verlag, EATCS Monogr. Theoret. Comput. Sci. (1993). | MR | Zbl
[6] and, Matrix and matricial iteration theories, Part I. J. Comput. System Sci. 46 (1993) 381-408. | MR | Zbl
[7] , and, Matrices, machines and behaviors. Appl. Categorical Structures 4 (1996) 343-360. | MR | Zbl
[8] , and, Feedback for linearly distributive categories: Traces and fixpoints. J. Pure Appl. Algebra 154 (2000) 27-69. | MR | Zbl
[9] and, Cartesian Bicategories I. J. Pure Appl. Algebra 49 (1987) 11-32. | MR | Zbl
[10] , Regular Algebra and Finite Machines. Chapman and Hall, London (1971). | Zbl
[11] , Monadic computation and iterative algebraic theories, edited by J.C. Shepherdson. North Holland, Amsterdam, Logic Colloquium 1973, Studies in Logic 80 (1975). | MR | Zbl
[12] , Matricial Theories. J. Algebra 42 (1976) 391-421. | MR | Zbl
[13] ,,, and, Comparing Cospan-spans and Tiles via a Hoare-style process calculus. TOSCA Udine, Electron. Notes Theoret. Comput. Sci. 62 (2001) 152-171.
[14] , Models of Sharing Graphs: A categorical semantics of let and letrec, Ph.D. Thesis. Edinburgh (1997), Springer (1999). | MR | Zbl
[15] , and, Traced monoidal categories. Math. Proc. Camb. Phil. Soc. 119 (1996) 447-468. | MR | Zbl
[16] and, Braided tensor categories. Adv. in Math. 102 (1993) 20-78. | MR | Zbl
[17] and, An imperative language based on distributive categories II. RAIRO: Theoret. Informatics Appl. 27 (1993) 503-522. | Numdam | MR | Zbl
[18] , and, Bicategories of processes. J. Pure Appl. Algebra 115 (1997) 141-178. | MR | Zbl
[19] , and, 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. | Zbl
[20] , and, On the algebra of systems with feedback and boundary. Rend. Circ. Mat. Palermo (2) Suppl. 63 (2000) 123-156. | MR | Zbl
[21] , and, 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] , and, Recursion and concurrency, Invited talk, FICS 2001. Florence (2001).
[23] and, The compact closed bicategory of left adjoints. Math. Proc. Camb. Phil. Soc. 130 (2001) 77-87. | MR | Zbl
[24] and, Coherence for compact closed categories. J. Pure Appl. Algebra 19 (1980) 193-213. | MR | Zbl
[25] and, Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines. Trans. Amer. Math. Soc. 116 (1965) 450-464. | MR | Zbl
[26] , Local rings. Interscience (1962). | MR | Zbl
[27] , Applications of negative dimensional torsors, edited by D.J.A. Welsh. Academic Press, New York, Comb. Math. Appl. (1971) 221-244. | MR | Zbl
[28] , Linear System Theory, Second Edition. Prentice Hall (1996). | MR | Zbl
[29] , 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. | MR
[30] , and, A note on recursive functions. Math. Struct. Comput. Sci. 6 (1996) 127-139. | MR | Zbl
[31] , An introduction to Automata Theory. Blackwell Scientic Publications, Oxford (1987).
[32] and, Complete axioms for categorical fixed-point operators, in Proc. 15th LICS (2000) 30-41. | MR
[33] , On flowchart theories I: The deterministic case. J. Comput. System Sci. 35 (1985) 163-191. | MR | Zbl
[34] , Network Algebra. Springer-Verlag (2000). | MR | Zbl
[35] , Categories and Computer Science. Carslaw Publications (1991), Cambridge University Press (1992). | MR | Zbl
Cité par Sources :
