Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-27T22:09:02.609Z Has data issue: false hasContentIssue false
  • English
  • Français

Event structures and non-orthogonal term graph rewriting

Published online by Cambridge University Press:  19 April 2018

David Clark  and
Richard Kennaway
David Clark
Affiliation:
Department of Computing, Imperial College, London, UK
Richard Kennaway
Affiliation:
School of Information Systems, University of East Anglia, Norwich, UK
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that for every term graph in a left-linear but non-orthogonal term graph rewrite system, one can construct an event structure that represents all the possible reductions that can occur in reduction sequences starting from that term graph. Every finite reduction sequence from that graph corresponds to a configuration of the event structure, and Lévy-equivalent sequences correspond to the same configuration.

Garbage collection is modelled in the event structure by an ‘erases’ relation. The asymmetric conflicts that arise in non-orthogonal rewrite systems are modelled by introducing a ‘prevents’ relation. The configurations of the event structure then form the state space of an event automaton. Taking the directed completion of this space yields a prime algebraic domain.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 6 , Issue 6 , December 1996 , pp. 545 - 578
Copyright
Copyright © Cambridge University Press 1996

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

Barendregt, H. P. (1984) The Lambda Calculus (2nd edition). Studies in Logic and the Foundations of Mathematics 103, Elsevier Science Publishers.Google Scholar
Barendregt, H. P., van Eekelen, M. C. J. D., Glauert, J. R. W., Kennaway, J. R., Plasmeijer, M. J. and Sleep, M. R. (1987) Term graph rewriting. In: Proceedings of PARLE 87, volume 2. Springer-Verlag Lecture Notes in Computer Science 259 141–158.Google Scholar
Boudol, G. (1985) Computational semantics of term rewriting systems. In: Nivat, M. and Reynolds, J. C. (eds.) Algebraic Methods in Semantics, chapter 5, Cambridge University Press 169–236.Google Scholar
Corradini, A. (1994) Term rewriting, in parallel. Unpublished draft, available by application to the author at .Google Scholar
van Eekelen, M. C. J. D., Nocker, E., Smetsers, J. E. W. and Plasmeijer, M. J. (1991) Concurrent clean. In: Proceedings of Parallel Architectures and Languages Europe (PARLE ’91). Springer-Verlag Lecture Notes in Computer Science 505 202–219.Google Scholar
Glauert, J. R. W. and Khasidashvih, Z. (1993) Optimal normalization in orthogonal term rewriting systems. In: Kirchner, C. (ed.) Proc. 5th Conference on Rewriting techniques and applications. Springer-Verlag Lecture Notes in Computer Science 690 243–258.Google Scholar
Gonthier, G., Levy, J.-J. and Mellies, P. A. (1992) An abstract standardisation theorem. In: Seventh annual IEEE Symposium on Logic in Computer Science. Google Scholar
Hankin, C. L. (1993) Graph rewriting systems and abstract interpretation. In: Gay, S., Burn, G. and Ryan, M. (eds.) Proceedings of the First Imperial College Department of Computing Workshop on Theory and Formal Methods, Workshops in Computing, Isle of Thorns, Sussex, UK, Springer-Verlag 27–36.Google Scholar
Huet, G. (1980) Confluent reductions: abstract properties and applications to term rewriting systems. Journal of the Association for Computing Machinery 27 797–821.CrossRefGoogle Scholar
Huet, G. and Levy, J.-J. (1991) Computations in orthogonal rewriting systems: I and II. In: Lassez, J. and Plotkin, G. D. (eds.) Computational Logic: Essays in Honor of Alan Robinson, MIT Press 394–443.Google Scholar
Kennaway, J. R. (1991) Graph rewriting in some categories of partial morphisms. In: International Workshop on Graph Grammars and their Application to Computer Science. Springer-Verlag Lecture Notes in Computer Science 532 490–504.CrossRefGoogle Scholar
Kennaway, J. R., Klop, J. W., Sleep, M. R. and de Vries, F. J. (1993) Event structures and orthogonal term graph rewriting. In: Term Graph Rewriting, Theory and Practice, John Wiley and Sons 141–155.Google Scholar
Nocker, E. (1993) Strictness analysis using abstract reduction. In: Proceedings of Conference on Functional Programming Languages and Computer Architectures (FPCA ’93), Copenhagen, ACM Press.Google Scholar
Nocker, E. (1994) Efficient Functional Programming, Ph.D. thesis, Department of Computer Science, University of Nijmegen, The Netherlands.Google Scholar
Pinna, G. and Poigné, A. (1992) On the nature of events. In: Mathematical Foundations of Computer Science. Springer-Verlag Lecture Notes in Computer Science 629. Google Scholar
Pinna, G. and Poigné, A. (1993) The mathematics of event automata. Presented at CTCS'93.Google Scholar
Pinna, G. and Poigné, A. (1995) On the nature of events: Another perspective in concurrency. Theoretical Computer Science 138 425–454.CrossRefGoogle Scholar
Winskel, G. (1986) Event structures. Technical Report 95, University of Cambridge Computer Laboratory.Google Scholar
Winskel, G. (1987) Event structures. In: Advances in Petri Nets, 1986, Part II. Springer-Verlag Lecture Notes in Computer Science 255.CrossRefGoogle Scholar
Winskel, G. (1988) An introduction to event structures. In: Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, REX Workshop. Springer-Verlag Lecture Notes in Computer Science 354 364.CrossRefGoogle Scholar