Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-27T09:44:24.987Z Has data issue: false hasContentIssue false
  • English
  • Français

Feedback, trace and fixed-point semantics

Published online by Cambridge University Press:  15 December 2002

P. Katis ,
Nicoletta Sabadini  and
Robert F.C. Walters
P. Katis
Affiliation:
Dipartimento di Scienze CC. FF.MM.,Università degli Studi dell'Insubria, Como, Italy; [email protected]@uninsubria.it.
Nicoletta Sabadini
Affiliation:
Dipartimento di Scienze CC. FF.MM.,Università degli Studi dell'Insubria, Como, Italy; [email protected]@uninsubria.it.
Robert F.C. Walters
Affiliation:
Dipartimento di Scienze CC. FF.MM.,Università degli Studi dell'Insubria, Como, Italy; [email protected]@uninsubria.it. School of Mathematics and Statistics, University of Sydney, NSW 2006, Australia.
Get access

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.

Keywords

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 36 , Issue 2: Fixed Points in Computer Science (FICS'01) , April 2002 , pp. 181 - 194
Copyright
© EDP Sciences, 2002

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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 CrossRef
Bartha, M., An algebraic model of synchronous systems. Inform. and Comput. 97 (1992) 97-131. CrossRef
Bernatsky, L. and Ésik, Z., Sematics of flowchart programs and the free Conway theories. RAIRO: Theoret. Informatics Applic. 32 (1998) 35-78.
Bloom, S.L. and Ésik, Z., Axiomatising schemes and their behaviours. J. Comput. System Sci. 31 (1985) 375-393. CrossRef
S.L. Bloom and Z. Ésik, Iteration Theories: The Equational Logic of Iterative Processes. Springer-Verlag, EATCS Monogr. Theoret. Comput. Sci. (1993).
Bloom, S.L. and Ésik, Z., Matrix and matricial iteration theories, Part I. J. Comput. System Sci. 46 (1993) 381-408. CrossRef
Bloom, S.L., Sabadini, N. and Walters, R.F.C., Matrices, machines and behaviors. Appl. Categorical Structures 4 (1996) 343-360. CrossRef
Blute, R.F., Cockett, J.R.B. and Seely, R.A.G., Feedback for linearly distributive categories: Traces and fixpoints. J. Pure Appl. Algebra 154 (2000) 27-69. CrossRef
Carboni, A. and Walters, R.F.C., Cartesian Bicategories I. J. Pure Appl. Algebra 49 (1987) 11-32. CrossRef
J. Conway, Regular Algebra and Finite Machines. Chapman and Hall, London (1971).
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).
Elgot, C.C., Matricial Theories. J. Algebra 42 (1976) 391-421. CrossRef
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.
M. Hasegawa, Models of Sharing Graphs: A categorical semantics of let and letrec,Ph.D. Thesis. Edinburgh (1997), Springer (1999).
Joyal, A., Street, R. and Verity, D., Traced monoidal categories. Math. Proc. Camb. Phil. Soc. 119 (1996) 447-468. CrossRef
Joyal, A. and Street, R., Braided tensor categories. Adv. in Math. 102 (1993) 20-78. CrossRef
Khalil, W. and Walters, R.F.C., An imperative language based on distributive categories II. RAIRO: Theoret. Informatics Appl. 27 (1993) 503-522.
Katis, P., Sabadini, N. and Walters, R.F.C., Bicategories of processes. J. Pure Appl. Algebra 115 (1997) 141-178. CrossRef
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.
Katis, P., Sabadini, N. and Walters, R.F.C., On the algebra of systems with feedback and boundary. Rend. Circ. Mat. Palermo (2) Suppl. 63 (2000) 123-156.
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).
Katis, P. and Walters, R.F.C., The compact closed bicategory of left adjoints. Math. Proc. Camb. Phil. Soc. 130 (2001) 77-87. CrossRef
Kelly, G.M. and Laplaza, M., Coherence for compact closed categories. J. Pure Appl. Algebra 19 (1980) 193-213. CrossRef
Krohn, K. and Rhodes, J., Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines. Trans. Amer. Math. Soc. 116 (1965) 450-464. CrossRef
M. Nagata, Local rings. Interscience (1962).
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).
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.
Sabadini, N., Vigna, S. and Walters, R.F.C., A note on recursive functions. Math. Struct. Comput. Sci. 6 (1996) 127-139. CrossRef
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. CrossRef
G. Stefanescu, Network Algebra. Springer-Verlag (2000).
R.F.C. Walters, Categories and Computer Science. Carslaw Publications (1991), Cambridge University Press (1992).