Rewriting on cyclic structures : equivalence between the operational and the categorical description
Corradini, Andrea ; Gadducci, Fabio
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999), p. 467-493 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1999-01-01
@article{ITA_1999__33_4-5_467_0,
     author = {Corradini, Andrea and Gadducci, Fabio},
     title = {Rewriting on cyclic structures : equivalence between the operational and the categorical description},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {33},
     year = {1999},
     pages = {467-493},
     mrnumber = {1748667},
     zbl = {0940.18002},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1999__33_4-5_467_0}
}

Corradini, Andrea; Gadducci, Fabio. Rewriting on cyclic structures : equivalence between the operational and the categorical description. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) pp. 467-493. http://gdmltest.u-ga.fr/item/ITA_1999__33_4-5_467_0/

[1] Z. M. Ariola and J. W. Klop, Equational term graph rewriting. Fund. Inform. 26 (1996) 207-240. | MR 1416136 | Zbl 0854.68049

[2] Z. M. Ariola, J. W. Klop and D. Plump, Confluent rewriting of bisimilar term graphs, C. Palamidessi and J. Parrow, Eds., Expressiveness in Concurrency. Elsevier Sciences, Electron. Notes Theoret. Comput. Sci. 7 (1997). Available at http://www.elsevier.nl/locate/entcs/volume7.html/. | MR 1492994 | Zbl 0911.68090

[3] H. P. Barendregt, M. C. J. D. Van Eekelen, J. R. W. Glauert, J. R. Kennaway, M. J. Plasrneijer and M. R. Sleep, Term graph reduction, J. W. de Bakker, A. J. Nijman and P. C. Treleaven, Eds., Parallel Architectures and Languages Europe. Springer Verlag, Lecture Notes in Comput Sci. 259 (1987) 141-158. | MR 910301

[4] L. Bernátsky and Z. Ésik, Semantics of flowchart programs and the free Conway theories. Theoret. Informatics Appl. 32 (1998) 35-78. | Numdam | MR 1657511

[5] G. Berry and J.-J. Lévy, Minimal and optimal computations of recursive programs. J. ACM 26 (1979) 148-175. | MR 514639 | Zbl 0388.68012

[6] S. Bloom and Z. Ésik, Axiomatizing schemes and their behaviors. J. Comput. System Sci. 31 (1985) 375-393. | MR 835132 | Zbl 0613.68013

[7] S. Bloom and Z. Ésik, Iteration Theories. EATCS Monographs on Theoretical Computer Science. Springer Verlag (1993). | MR 1295433 | Zbl 0773.03033

[8] S. Bloom and Z. Ésik, The equational logic of fixed points. Theoret. Comput. Sci. 179 (1997) 1-60. | MR 1454584 | Zbl 0920.03067

[9] S. L. Bloom, Z. Ésik, A. Labella and E. G. Manes, Iteration 2-theories, M. Johnson, Ed., Algebraic Methodology and Software Technology. Springer Verlag, Lecture Notes in Comput. Sci. 1349 (1997) 30-44. | MR 1812303 | Zbl 0885.18003

[10] G. Boudol, Computational semantics of term rewriting Systems, M. Nivat and J. Reynolds, Eds., Algebraic Methods in Semantics. Cambridge University Press (1985) 170-235. | MR 835452 | Zbl 0611.68007

[11] A. Corradini, Term rewriting in CT∑, M.-C.. Gaudel and J.-P. Jouannaud, Eds., Trees in Algebra and Programming. Springer Verlag, Lecture Notes in Comput. Sci. 668 (1993) 468-484. | MR 1236487

[12] A. Corradini and F. Drewes, (Cyclic) term graph rewriting is adequate for rational parallel term rewriting, Technical Report TR-97-14. Dipartimento di Informatica, Pisa (1997).

[13] A. Corradini and F. Gadducci, A 2-categorical presentation of term graph rewriting, E. Moggi and G. Rosolini, Eds., Category Theory and Computer Science. Springer Verlag, Lecture Notes in Comput Sci. 1290 (1997) 87-105. | MR 1640339 | Zbl 0889.68085

[14] A. Corradini and F. Gadducci, Rational term rewriting, M. Nivat, Ed., Foundations of Software Science and Computation Structures. Springer Verlag, Lecture Notes in Comput. Sci. 1378 (1998) 156-171. | MR 1641337 | Zbl 0908.68081

[15] A. Corradini and F. Gadducci, An algebraic presentation of term graphs, via gs-monoidal categories. Applied Categorical Structures, to appear. | MR 1752925 | Zbl 0949.68121

[16] A. Corradini, U. Montanari, F. Rossi, H. Ehrig, R. Heckel and M. Löwe, Algebraic approaches to graph transformation I: Basic concepts and double pushout approach, G. Rozenberg, Ed., Handbook of Graph Grammars and Computing by Graph Transformation 1. World Scientific (1997). | MR 1480955

[17] A. Corradini and F. Rossi, Hyperedge replacement jungle rewriting for term rewriting Systems and logic programming. Theoret. Comput Sci. 109 (1993) 7-48. | MR 1205620 | Zbl 0781.68074

[18] Gh. Ştefănescu, On flowchart theories: Part II. The nondeterministic case. Theoret. Comput. Sci. 52 (1987307-340. | MR 918108 | Zbl 0642.68020

[19] Gh. Ştefănescu, Algebra of flownomials. Technical Report SFB-Bericht 342/16/94 A. Technical University of München, Institut für Informatik (1994).

[20] V.-E. Căzănescu and Gh. Ştefănescu, Towards a new algebraic foundation of nowchart scheme theory. Fund. Inform. 13 (1990) 171-210. | MR 1074634 | Zbl 0705.68071

[21] V.-E. Căzănescu and Gh. Ştefănescu, A general result on abstract flowchart schemes with applications to the study of accessibility, reduction and minimization. Theoret Comput. Sci. 99 (1992) 1-63. | MR 1168009 | Zbl 0770.68037

[22] V.-E. Căzănescu and Gh. Ştefănescu, Feedback, iteration and repetition, Gh. Paun, Ed., Mathematical Aspects of Natural and Formal Languages. World Scientific (1995) 43-62.

[23] C. C. Elgot, Monadic computations and iterative algebraic theories, H. E. Rose and J. C. Shepherdson, Eds., Logic Colloquium 1973. North Holland, Stud. Logic Found. Math. 80 (1975) 175-230. | MR 413584 | Zbl 0327.02040

[24] C. C. Elgot, Structured programming with and without GO TO statements. IEEE Trans. Software Engrg. 2 (1976) 41-54. | MR 433942 | Zbl 0348.68008

[25] C. C. Elgot, C. C. Bloom and R. Tindell, The algebraic structure of rooted trees. J. Comput. System Sci. 16 (1978) 362-339. | MR 496954 | Zbl 0389.68007

[26] Z. Ésik, Identities in iterative theories and rational algebraic theories. Computational Linguistics and Computer Languages 14 (1980) 183-207. | MR 626263 | Zbl 0466.68010

[27] Z. Ésik, Group axioms for iteration. Inform. and Comput 148 (1999) 131-180. | MR 1674307 | Zbl 0924.68143

[28] Z. Ésik and A. Labella, Equational properties of iteration in algebraically complete categories. Theoret Comput. Sci. 195 (1998) 61-89. | MR 1603831 | Zbl 0903.18003

[29] W. M. Farmer, J. D. Ramsdell and R. J. Watro, A correetness proof for combinator reduction with cycles. ACM Trans. Program. Lang. Syst 12 (1990) 123-134.

[30] W. M. Farmer and R. J. Watro, Redex capturing in term graph rewriting, R.V. Book, Ed., Rewriting Techniques and Applications. Springer Verlag, Lecture Notes in Comput. Sci. 488 (1991) 13-24. | MR 1104466

[31] S. Ginali, Regular trees and the free iterative theory. J. Comput System Sci. 18 (1979) 222-242. | MR 536398 | Zbl 0495.68042

[32] J. A. Goguen, J. W. Tatcher, E. G. Wagner and J. R Wright, Initial algebra semantics and continuous algebras. J. ACM 24 (1977) 68-95. | MR 520711 | Zbl 0359.68018

[33] I. Guessarian, Algebraic Semantics. Springer Verlag, Lecture Notes in Comput. Sci. 99 (1981). | MR 617908 | Zbl 0474.68010

[34] M. Hasegawa, Models of Sharing Graphs. Ph. D. Thesis, University of Edinburgh, Department of Computer Science (1997).

[35] M. Hasegawa, Recursion from cyclic sharing: Traced monoidal categories and models of cyclic lambda-calculus, Ph. de Groote and R. Hindly, Eds., Typed Lambda Calculi and Applications. Springer Verlag, Lecture Notes in Comput. Sci. 1210 (1997) 196-213. | MR 1480472 | Zbl 1063.68599

[36] B. Hoffmann and D. Plump, Implementing term rewriting by jungle evaluation. Theoret. Informatics Appl 25 (1991) 445-472. | Numdam | MR 1144009 | Zbl 0706.68061

[37] A. Joyal, R. H. Street and D. Verity, Traced monoidal categories. Math. Proc. Cambridge Philos. Soc. 119 (1996) 425-446. | MR 1357057 | Zbl 0845.18005

[38] G. Kelly, Basic Concepts of Enriched Category Theory. Cambridge University Press (1982). | MR 651714 | Zbl 0478.18005

[39] G. M. Kelly and R. H. Street, Review of the elements of 2-categories, G. M. Kelly, Ed., Sydney Category Seminar. Springer Verlag, Lecture Notes in Math. 420 (1974) 75-103. | MR 357542 | Zbl 0334.18016

[40] J. R. Kennaway, On "On Graph Rewritings". Theoret Comput Sci. 52 (1980) 37-58. | MR 918112 | Zbl 0636.68028

[41] J. R. Kennaway, J. W. Klop, M. R. Sleep and F. J. De Vries, On the adequacy of graph rewriting for simulating term rewriting. ACM Trans. Program. Lang. Syst. 16 (1994) 493-523.

[42] J. W. Klop, Term rewriting Systems, S. Abramsky, D. Gabbay and T. Maibaum, Eds. Oxford University Press, Handb. Log. Comput Sci. 1 (1992) 1-116. | MR 1381696

[43] N. Martí-Oliet and J. Meseguer, From Petri nets to linear logic through categories: A survey. Intrenat J. Foundations Comput. Sci. 4 (1991) 297-399. | MR 1160674 | Zbl 0766.68100

[44] J. Meseguer, Conditional rewriting logic as a unified model of concurrency. Theoret. Comput. Sci. 96 (1992) 73-155. | MR 1158714 | Zbl 0758.68043

[45] J. Meseguer and U. Montanari, Petri nets are monoids. Inform. and Comput 88 (1990) 105-155. | MR 1070245 | Zbl 0711.68077

[46] H. Miyoshi, Rewriting logic for cyclic sharing structures, T. Sato and A. Middeldorp, Eds., Fuji International Symposium on Functional and Logic Programming. World Scientific (1998) 167-186.

[47] U. Montanari and F. Rossi, Contextual nets. Acta Inform. 32 (1995) 545-596. | MR 1351560 | Zbl 0835.68084

[48] M. J. Plasmeijer and M. C. J. D. Van Eekelen, Functional Programming and Parallel Graph Rewriting. Addison Wesley (1993). | Zbl 0788.68023

[49] A. J. Power, An abstract formulation for rewrite Systems, D. H. Pitt, D. E. Rydehard, P. Dybjer, A. M. Pitts and A. Poigné, Eds., Category Theory and Computer Science. Springer Verlag, Lecture Notes in Comput. Sci. 389 (1989) 300-312. | MR 1031569

[50] W. Reisig, Petri Nets: An Introduction. EACTS Monographs on Theoretical Computer Science. Springer Verlag (1985). | MR 782303 | Zbl 0555.68033

[51] D. E. Rydehard and E. G. Stell, Foundations of equational deductions: A categorical treatment of equational proofs and unification algorithms, D. H. Pitt, A. Poigne and D. E. Rydehard, Eds., Category Theory and Computer Science. Springer Verlag, Lecture Notes in Comput Sci. 283 (1987) 114-139. | MR 925227 | Zbl 0664.03041

[52] D. Scott, The lattice of flow diagrams, E. Engeler, Ed., Semantics of Algorithmic Languages, Springer Verlag, Lecture Notes in Math. 182 (1971) 311-366. | MR 278849 | Zbl 0228.68016

[53] M. R. Sleep, M. J. Plasmeijer and M. C. Van Eekelen, Term Graph Rewriting: Theory and Practice. Wiley (1993). | MR 1224026 | Zbl 0818.68099

[54] J. Staples, Computation of graph-like expressions. Theoret. Comput Sci. 10 (1980) 171-195. | MR 551603 | Zbl 0423.68007

[55] J. Staples, Optimal evaluation of graph-like expressions. Theoret. Comput. Sci. 10 (1980) 297-316. | MR 559691 | Zbl 0426.68006

[56] J. Staples, Speeding up subtree replacement systems. Theoret. Comput. Sci. 11 (1980) 39-47. | MR 566691 | Zbl 0438.68032

[57] R. H. Street, Categorical structures, M. Hazewinkel, Ed., Handbook of Algebra. Elsevier (1996) 529-577. | MR 1421811 | Zbl 0854.18001

[58] D. A. Turner, A new implementation technique for applicative languages. Software: Practice and Experience 9 (1979) 31-49. | Zbl 0386.68009

[59] M. Wand, A concrete approach to abstract recursive definitions, M. Nivat, Ed., Automata, Languages and Programming. North Holland (1973) 331-341. | MR 366767 | Zbl 0278.68066