Rewriting on cyclic structures : equivalence between the operational and the categorical description

 Access to full text

 Full (PDF)

1. [1] Z. M. Ariola and J. W. Klop, Equational term graph rewriting. Fund. Inform. 26 (1996) 207-240. Zbl0854.68049MR1416136
2. [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/. Zbl0911.68090MR1492994
3. [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. MR910301
4. [4] L. Bernátsky and Z. Ésik, Semantics of flowchart programs and the free Conway theories. Theoret. Informatics Appl. 32 (1998) 35-78. MR1657511
5. [5] G. Berry and J.-J. Lévy, Minimal and optimal computations of recursive programs. J. ACM 26 (1979) 148-175. Zbl0388.68012MR514639
6. [6] S. Bloom and Z. Ésik, Axiomatizing schemes and their behaviors. J. Comput. System Sci. 31 (1985) 375-393. Zbl0613.68013MR835132
7. [7] S. Bloom and Z. Ésik, Iteration Theories. EATCS Monographs on Theoretical Computer Science. Springer Verlag (1993). Zbl0773.03033MR1295433
8. [8] S. Bloom and Z. Ésik, The equational logic of fixed points. Theoret. Comput. Sci. 179 (1997) 1-60. Zbl0920.03067MR1454584
9. [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. Zbl0885.18003MR1812303
10. [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. Zbl0611.68007MR835452
11. [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. MR1236487
12. [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. [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. Zbl0889.68085MR1640339
14. [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. Zbl0908.68081MR1641337
15. [15] A. Corradini and F. Gadducci, An algebraic presentation of term graphs, via gs-monoidal categories. Applied Categorical Structures, to appear. Zbl0949.68121MR1752925
16. [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). MR1480955
17. [17] A. Corradini and F. Rossi, Hyperedge replacement jungle rewriting for term rewriting Systems and logic programming. Theoret. Comput Sci. 109 (1993) 7-48. Zbl0781.68074MR1205620
18. [18] Gh. Ştefănescu, On flowchart theories: Part II. The nondeterministic case. Theoret. Comput. Sci. 52 (1987307-340. Zbl0642.68020MR918108
19. [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. [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. Zbl0705.68071MR1074634
21. [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. Zbl0770.68037MR1168009
22. [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. [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. Zbl0327.02040MR413584
24. [24] C. C. Elgot, Structured programming with and without GO TO statements. IEEE Trans. Software Engrg. 2 (1976) 41-54. Zbl0348.68008MR433942
25. [25] C. C. Elgot, C. C. Bloom and R. Tindell, The algebraic structure of rooted trees. J. Comput. System Sci. 16 (1978) 362-339. Zbl0389.68007MR496954
26. [26] Z. Ésik, Identities in iterative theories and rational algebraic theories. Computational Linguistics and Computer Languages 14 (1980) 183-207. Zbl0466.68010MR626263
27. [27] Z. Ésik, Group axioms for iteration. Inform. and Comput 148 (1999) 131-180. Zbl0924.68143MR1674307
28. [28] Z. Ésik and A. Labella, Equational properties of iteration in algebraically complete categories. Theoret Comput. Sci. 195 (1998) 61-89. Zbl0903.18003MR1603831
29. [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. [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. MR1104466
31. [31] S. Ginali, Regular trees and the free iterative theory. J. Comput System Sci. 18 (1979) 222-242. Zbl0495.68042MR536398
32. [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. Zbl0359.68018MR520711
33. [33] I. Guessarian, Algebraic Semantics. Springer Verlag, Lecture Notes in Comput. Sci. 99 (1981). Zbl0474.68010MR617908
34. [34] M. Hasegawa, Models of Sharing Graphs. Ph. D. Thesis, University of Edinburgh, Department of Computer Science (1997). 
35. [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. Zbl1063.68599MR1480472
36. [36] B. Hoffmann and D. Plump, Implementing term rewriting by jungle evaluation. Theoret. Informatics Appl 25 (1991) 445-472. Zbl0706.68061MR1144009
37. [37] A. Joyal, R. H. Street and D. Verity, Traced monoidal categories. Math. Proc. Cambridge Philos. Soc. 119 (1996) 425-446. Zbl0845.18005MR1357057
38. [38] G. Kelly, Basic Concepts of Enriched Category Theory. Cambridge University Press (1982). Zbl0478.18005MR651714
39. [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. Zbl0334.18016MR357542
40. [40] J. R. Kennaway, On "On Graph Rewritings". Theoret Comput Sci. 52 (1980) 37-58. Zbl0636.68028MR918112
41. [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. [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. MR1381696
43. [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. Zbl0766.68100MR1160674
44. [44] J. Meseguer, Conditional rewriting logic as a unified model of concurrency. Theoret. Comput. Sci. 96 (1992) 73-155. Zbl0758.68043MR1158714
45. [45] J. Meseguer and U. Montanari, Petri nets are monoids. Inform. and Comput 88 (1990) 105-155. Zbl0711.68077MR1070245
46. [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. [47] U. Montanari and F. Rossi, Contextual nets. Acta Inform. 32 (1995) 545-596. Zbl0835.68084MR1351560
48. [48] M. J. Plasmeijer and M. C. J. D. van Eekelen, Functional Programming and Parallel Graph Rewriting. Addison Wesley (1993). Zbl0788.68023
49. [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. MR1031569
50. [50] W. Reisig, Petri Nets: An Introduction. EACTS Monographs on Theoretical Computer Science. Springer Verlag (1985). Zbl0555.68033MR782303
51. [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. Zbl0664.03041MR925227
52. [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. Zbl0228.68016MR278849
53. [53] M. R. Sleep, M. J. Plasmeijer and M. C. van Eekelen, Term Graph Rewriting: Theory and Practice. Wiley (1993). Zbl0818.68099MR1224026
54. [54] J. Staples, Computation of graph-like expressions. Theoret. Comput Sci. 10 (1980) 171-195. Zbl0423.68007MR551603
55. [55] J. Staples, Optimal evaluation of graph-like expressions. Theoret. Comput. Sci. 10 (1980) 297-316. Zbl0426.68006MR559691
56. [56] J. Staples, Speeding up subtree replacement systems. Theoret. Comput. Sci. 11 (1980) 39-47. Zbl0438.68032MR566691
57. [57] R. H. Street, Categorical structures, M. Hazewinkel, Ed., Handbook of Algebra. Elsevier (1996) 529-577. Zbl0854.18001MR1421811
58. [58] D. A. Turner, A new implementation technique for applicative languages. Software: Practice and Experience 9 (1979) 31-49. Zbl0386.68009
59. [59] M. Wand, A concrete approach to abstract recursive definitions, M. Nivat, Ed., Automata, Languages and Programming. North Holland (1973) 331-341. Zbl0278.68066MR366767