From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/1232 Path: news.gmane.org!not-for-mail From: Fabio Gadducci Newsgroups: gmane.science.mathematics.categories Subject: paper announcement Date: Fri, 01 Oct 1999 18:30:06 +0000 Organization: Division of Informatics, The University of Edinburgh Message-ID: <37F4FDAE.228E804D@dcs.ed.ac.uk> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1241017657 30071 80.91.229.2 (29 Apr 2009 15:07:37 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:07:37 +0000 (UTC) To: Categories List Original-X-From: cat-dist Fri Oct 1 19:01:38 1999 Original-Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id RAA24105 for categories-list; Fri, 1 Oct 1999 17:34:31 -0300 (ADT) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f X-Mailer: Mozilla 4.61 [en] (X11; I; Linux 2.0.35 i686) X-Accept-Language: en Original-Sender: cat-dist@mta.ca Precedence: bulk Original-Lines: 40 Xref: news.gmane.org gmane.science.mathematics.categories:1232 Archived-At: Dear members of the mailing list, I'm pleased to annouce that the paper ``Rewriting on Cyclic Structures'', by myself and Andrea Corradini, is available at http://www.di.unipi.it/~gadducci/papers/RAIRO.ps. The abstract follows, but shortly, it uses traced monoidal 2-categories --where, in addition, each object ha`s a comonoidal structure-- in order to simulate various kinds of (eventually cyclic) term (graph) rewriting. Its interest for a broader audience may lie, besides in showing a practical application of the trace structure in the rewriting field, in its appendix, where we tried to sketch a very SHORT history of the notion of feedback in theoretical computer science, with a particular attention to the algebraic specification field. We found it interesting to review previous approaches to the topic, after the results of Joyal-Street-Verity have newly sparkled the interest in the algebraic description of fixed points (see e.g. the recent paper by Selinger advertised a few weeks ago on this mailing list). Best regards, Fabio Gadducci xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx \begin{abstract} We present a categorical formulation of the rewriting of possibly cyclic term graphs, based on a variation of algebraic 2-theories. We show that this presentation is equivalent to the well-accepted operational definition proposed by Barendregt et alii---but for the case of ``circular redexes'', for which we propose (and justify formally) a different treatment. The categorical framework allows us to model in a concise way also automatic garbage collection and rules for sharing/unsharing and folding/unfolding of structures, and to relate term graph rewriting to other rewriting formalisms. \end{abstract}