{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T03:48:27Z","timestamp":1648957707937},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2018,4,19]],"date-time":"2018-04-19T00:00:00Z","timestamp":1524096000000},"content-version":"unspecified","delay-in-days":7809,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[1996,12]]},"abstract":"<jats:p>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\u00e9vy-equivalent sequences correspond to the same configuration.<\/jats:p><jats:p>Garbage collection is modelled in the event structure by an \u2018erases\u2019 relation. The asymmetric conflicts that arise in non-orthogonal rewrite systems are modelled by introducing a \u2018prevents\u2019 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.<\/jats:p>","DOI":"10.1017\/s0960129500070092","type":"journal-article","created":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T15:42:44Z","timestamp":1557675764000},"page":"545-578","source":"Crossref","is-referenced-by-count":6,"title":["Event structures and non-orthogonal term graph rewriting"],"prefix":"10.1017","volume":"6","author":[{"given":"David","family":"Clark","sequence":"first","affiliation":[]},{"given":"Richard","family":"Kennaway","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,4,19]]},"reference":[{"key":"S0960129500070092_ref007","unstructured":"Gonthier G. , Levy J.-J. and Mellies P. A. (1992) An abstract standardisation theorem. In: Seventh annual IEEE Symposium on Logic in Computer Science."},{"key":"S0960129500070092_ref015","volume-title":"Mathematical Foundations of Computer Science","volume":"629.","author":"Pinna","year":"1992"},{"key":"S0960129500070092_ref013","volume-title":"Proceedings of Conference on Functional Programming Languages and Computer Architectures (FPCA \u201993)","author":"Nocker","year":"1993"},{"key":"S0960129500070092_ref018","unstructured":"Winskel G. (1986) Event structures. Technical Report 95, University of Cambridge Computer Laboratory."},{"key":"S0960129500070092_ref010","first-page":"394","volume-title":"Computational Logic: Essays in Honor of Alan Robinson","author":"Huet","year":"1991"},{"key":"S0960129500070092_ref002","first-page":"141","volume-title":"Proceedings of PARLE 87, volume 2","volume":"259","author":"Barendregt","year":"1987"},{"key":"S0960129500070092_ref019","doi-asserted-by":"crossref","unstructured":"Winskel G. (1987) Event structures. In: Advances in Petri Nets, 1986, Part II. Springer-Verlag Lecture Notes in Computer Science 255.","DOI":"10.1007\/3-540-17906-2_31"},{"key":"S0960129500070092_ref003","first-page":"169","volume-title":"Algebraic Methods in Semantics","author":"Boudol","year":"1985"},{"key":"S0960129500070092_ref005","first-page":"202","volume-title":"Concurrent clean. In: Proceedings of Parallel Architectures and Languages Europe (PARLE \u201991)","volume":"505","author":"van Eekelen","year":"1991"},{"key":"S0960129500070092_ref006","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/3-540-56868-9_19","volume-title":"Proc. 5th Conference on Rewriting techniques and applications","volume":"690","author":"Glauert","year":"1993"},{"key":"S0960129500070092_ref008","first-page":"27","volume-title":"Proceedings of the First Imperial College Department of Computing Workshop on Theory and Formal Methods","author":"Hankin","year":"1993"},{"key":"S0960129500070092_ref009","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322230"},{"key":"S0960129500070092_ref011","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0017408"},{"key":"S0960129500070092_ref017","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00174-H"},{"key":"S0960129500070092_ref012","first-page":"141","volume-title":"Term Graph Rewriting, Theory and Practice","author":"Kennaway","year":"1993"},{"key":"S0960129500070092_ref001","volume-title":"Studies in Logic and the Foundations of Mathematics","volume":"103","author":"Barendregt","year":"1984"},{"key":"S0960129500070092_ref014","unstructured":"Nocker E. (1994) Efficient Functional Programming, Ph.D. thesis, Department of Computer Science, University of Nijmegen, The Netherlands."},{"key":"S0960129500070092_ref020","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0013026"},{"key":"S0960129500070092_ref016","unstructured":"Pinna G. and Poign\u00e9 A. (1993) The mathematics of event automata. Presented at CTCS'93."},{"key":"S0960129500070092_ref004","unstructured":"Corradini A. (1994) Term rewriting, in parallel. Unpublished draft, available by application to the author at andrea@DI.UniPi.IT."}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129500070092","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,12]],"date-time":"2019-05-12T15:43:10Z","timestamp":1557675790000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129500070092\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,12]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1996,12]]}},"alternative-id":["S0960129500070092"],"URL":"https:\/\/doi.org\/10.1017\/s0960129500070092","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,12]]}}}