{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:39:39Z","timestamp":1753889979401,"version":"3.41.2"},"reference-count":32,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2012,6,1]],"date-time":"2012-06-01T00:00:00Z","timestamp":1338508800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Term graph rewriting provides a simple mechanism to finitely represent\nrestricted forms of infinitary term rewriting. The correspondence between\ninfinitary term rewriting and term graph rewriting has been studied to some\nextent. However, this endeavour is impaired by the lack of an appropriate\ncounterpart of infinitary rewriting on the side of term graphs. We aim to fill\nthis gap by devising two modes of convergence based on a partial order\nrespectively a metric on term graphs. The thus obtained structures generalise\ncorresponding modes of convergence that are usually studied in infinitary term\nrewriting. We argue that this yields a common framework in which both term\nrewriting and term graph rewriting can be studied. In order to substantiate our\nclaim, we compare convergence on term graphs and on terms. In particular, we\nshow that the modes of convergence on term graphs are conservative extensions\nof the corresponding modes of convergence on terms and are preserved under\nunravelling term graphs to terms. Moreover, we show that many of the properties\nknown from infinitary term rewriting are preserved. This includes the intrinsic\ncompleteness of both modes of convergence and the fact that convergence via the\npartial order is a conservative extension of the metric convergence.<\/jats:p>","DOI":"10.2168\/lmcs-8(2:6)2012","type":"journal-article","created":{"date-parts":[[2013,9,23]],"date-time":"2013-09-23T14:50:43Z","timestamp":1379947843000},"source":"Crossref","is-referenced-by-count":1,"title":["Modes of Convergence for Term Graph Rewriting"],"prefix":"10.46298","volume":"Volume 8, Issue 2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1600-8261","authenticated-orcid":false,"given":"Patrick","family":"Bahr","sequence":"first","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2012,6,1]]},"reference":[{"key":"10.2168\/LMCS-8(2:6)2012_ariola05ptc","doi-asserted-by":"crossref","unstructured":"Zena Ariola and Stefan Blom. Skew and\u00f8mega-Skew Confluence and Abstract B\u00f6hm Semantics. In Aart Middeldorp, Vincent van Oostrom, Femke van Raamsdonk, and Roel de Vrijer, editors,Processes, Terms and Cycles: Steps on the Road to Infinity, volume 3838 ofLecture Notes in Computer Science, pages 368-403. Springer Berlin \/ Heidelberg, 2005.","DOI":"10.1007\/11601548_19"},{"issue":"1-3","key":"10.2168\/LMCS-8(2:6)2012_ariola02apal","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/S0168-0072(01)00104-X","volume":"117","author":"Zena M Ariola and Stefan Blom","year":"2002","journal-title":"Ann. Pure Appl. Logic"},{"issue":"2","key":"10.2168\/LMCS-8(2:6)2012_ariola97ic","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1006\/inco.1997.2651","volume":"139","author":"Zena M Ariola and Jan Willem Klop","year":"1997","journal-title":"Inf. Comput."},{"issue":"4","key":"10.2168\/LMCS-8(2:6)2012_arnold80fi","first-page":"445","volume":"3","author":"Andr\u00e9 Arnold and Maurice Nivat","year":"1980","journal-title":"Fundam. Inf."},{"key":"10.2168\/LMCS-8(2:6)2012_bahr09master","unstructured":"Patrick Bahr. Infinitary Rewriting - Theory and Applications. Master's thesis, Vienna University of Technology, Vienna, 2009."},{"key":"10.2168\/LMCS-8(2:6)2012_bahr10rta","unstructured":"Patrick Bahr. Abstract Models of Transfinite Reductions. In Christopher Lynch, editor,Proceedings of the 21st International Conference on Rewriting Techniques and Applications, volume 6 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 49-66, Dagstuhl, Germany, 2010. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"10.2168\/LMCS-8(2:6)2012_bahr10rta2","unstructured":"Patrick Bahr. Partial Order Infinitary Term Rewriting and B\u00f6hm Trees. In Christopher Lynch, editor,Proceedings of the 21st International Conference on Rewriting Techniques and Applications, volume 6 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 67-84, Dagstuhl, Germany, 2010. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"10.2168\/LMCS-8(2:6)2012_bahr11rta","unstructured":"Patrick Bahr. Modes of Convergence for Term Graph Rewriting. In Manfred Schmidt-Schau\u00df, editor,22nd International Conference on Rewriting Techniques and Applications, volume 10 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 139-154, Dagstuhl, Germany, 2011. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"10.2168\/LMCS-8(2:6)2012_bahr12mscs","doi-asserted-by":"crossref","unstructured":"Patrick Bahr. Convergence in infinitary term graph rewriting systems is simple. Unpublished manuscript, available from the author's web site, 2012.","DOI":"10.4204\/EPTCS.110.4"},{"key":"10.2168\/LMCS-8(2:6)2012_bahr12rta","unstructured":"Patrick Bahr. Infinitary term graph rewriting is simple, sound and complete. RTA 2012, to appear, 2012."},{"key":"10.2168\/LMCS-8(2:6)2012_barendsen03book","unstructured":"Erik Barendsen. Term Graph Rewriting. In Terese, editor,Term Rewriting Systems, chapter 13, pages 712-743. Cambridge University Press, 2003."},{"key":"10.2168\/LMCS-8(2:6)2012_blom04rta","doi-asserted-by":"crossref","unstructured":"Stefan Blom. An Approximation Based Approach to Infinitary Lambda Calculi. In Vincent van Oostrom, editor,Rewriting Techniques and Applications, volume 3091 ofLecture Notes in Computer Science, pages 221-232. Springer Berlin \/ Heidelberg, 2004.","DOI":"10.1007\/978-3-540-25979-4_16"},{"issue":"1","key":"10.2168\/LMCS-8(2:6)2012_dershowitz91tcs","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0304-3975(91)90040-9","volume":"83","author":"Nachum Dershowitz, St\u00e9phane Kaplan, and","year":"1991","journal-title":"Theor. Comput. Sci."},{"key":"10.2168\/LMCS-8(2:6)2012_farmer90ijfocs","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1142\/S0129054190000266","volume":"1","author":"William M Farmer and Ronald J Watro","year":"1990","journal-title":"Internat. J. Found. Comput. Sci."},{"issue":"1","key":"10.2168\/LMCS-8(2:6)2012_goguen77jacm","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1145\/321992.321997","volume":"24","author":"Joseph A Goguen, James W Thatcher, Eric","year":"1977","journal-title":"J. ACM"},{"key":"10.2168\/LMCS-8(2:6)2012_henderson76popl","doi-asserted-by":"crossref","unstructured":"Peter Henderson and James H Morris Jr. A lazy evaluator. InProceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, pages 95-103, New York, NY, USA, 1976. ACM.","DOI":"10.1145\/800168.811543"},{"issue":"2","key":"10.2168\/LMCS-8(2:6)2012_hughes89cj","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1093\/comjnl\/32.2.98","volume":"32","author":"John Hughes","year":"1989","journal-title":"Comput. J."},{"issue":"1-2","key":"10.2168\/LMCS-8(2:6)2012_kahn93tcs","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0304-3975(93)90090-G","volume":"121","author":"Gilles Kahn and Gordon D Plotkin","year":"1993","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"10.2168\/LMCS-8(2:6)2012_kahrs07ai","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s00236-007-0043-2","volume":"44","author":"Stefan Kahrs","year":"2007","journal-title":"Acta Inform."},{"key":"10.2168\/LMCS-8(2:6)2012_kelley55book","unstructured":"John L Kelley.General Topology, volume 27 ofGraduate Texts in Mathematics. Springer-Verlag, 1955."},{"key":"10.2168\/LMCS-8(2:6)2012_kennaway92rep","unstructured":"Richard Kennaway. On transfinite abstract reduction systems. Technical report, CWI (Centre for Mathematics and Computer Science), Amsterdam, 1992."},{"key":"10.2168\/LMCS-8(2:6)2012_kennaway95segragra","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S1571-0661(05)80192-6","volume":"2","author":"Richard Kennaway","year":"1995","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"10.2168\/LMCS-8(2:6)2012_kennaway03book","unstructured":"Richard Kennaway and Fer-Jan de Vries. Infinitary Rewriting. In Terese, editor,Term Rewriting Systems, chapter 12, pages 668-711. Cambridge University Press, 1st edition, 2003."},{"issue":"1","key":"10.2168\/LMCS-8(2:6)2012_kennaway97tcs","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/S0304-3975(96)00171-5","volume":"175","author":"Richard Kennaway, Jan Willem Klop, M R S","year":"1997","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10.2168\/LMCS-8(2:6)2012_kennaway94toplas","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1145\/177492.177577","volume":"16","author":"Richard Kennaway, Jan Willem Klop, M Ron","year":"1994","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"1","key":"10.2168\/LMCS-8(2:6)2012_kennaway95ic","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1006\/inco.1995.1075","volume":"119","author":"Richard Kennaway, Jan Willem Klop, M Ron","year":"1995","journal-title":"Inf. Comput."},{"key":"10.2168\/LMCS-8(2:6)2012_lucas01rta","doi-asserted-by":"crossref","unstructured":"Salvador Lucas. Transfinite Rewriting Semantics for Term Rewriting Systems. In Aart Middeldorp, editor,Rewriting Techniques and Applications, volume 2051 ofLecture Notes in Computer Science, pages 216-230. Springer Berlin \/ Heidelberg, 2001.","DOI":"10.1007\/3-540-45127-7_17"},{"key":"10.2168\/LMCS-8(2:6)2012_marlow10haskell","unstructured":"Simon Marlow. Haskell 2010 Language Report, 2010. Simon Peyton-Jones.The Implementation of Functional Programming Languages. Prentice Hall, 1987."},{"key":"10.2168\/LMCS-8(2:6)2012_plasmeijer93book","unstructured":"Rinus Plasmeijer and Marko C J D van Eekelen.Functional Programming and Parallel Graph Rewriting. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1993."},{"key":"10.2168\/LMCS-8(2:6)2012_plump99hggcbgt","doi-asserted-by":"crossref","unstructured":"Detlef Plump. Term graph rewriting. In Hartmut Ehrig, Gregor Engels, Hans-J\u00f6rg Kreowski, and Grzegorz Rozenberg, editors,Handbook of Graph Grammars and Computing by Graph Transformation, Volume 2: Applications, Languages, and Tools, pages 3-61. World Scientific Publishing Co., Inc., River Edge, NJ, USA, 1999.","DOI":"10.1142\/9789812815149_0001"},{"key":"10.2168\/LMCS-8(2:6)2012_simonsen10rta","unstructured":"Jakob Grue Simonsen. Weak Convergence and Uniform Normalization in Infinitary Rewriting. In Christopher Lynch, editor,Proceedings of the 21st International Conference on Rewriting Techniques and Applications, volume 6 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 311-324, Dagstuhl, Germany, 2010. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"10.2168\/LMCS-8(2:6)2012_terese03book","unstructured":"Terese.Term Rewriting Systems. Cambridge University Press, 1st edition, 2003."}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/935\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/935\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:59:27Z","timestamp":1681243167000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/935"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,1]]},"references-count":32,"URL":"https:\/\/doi.org\/10.2168\/lmcs-8(2:6)2012","relation":{"is-same-as":[{"id-type":"arxiv","id":"1205.0357","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1205.0357","asserted-by":"subject"}],"is-part-of":[{"id-type":"doi","id":"10.4230\/lipics.rta.2011","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2012,6,1]]},"article-number":"935"}}