Subject: categories: paper announcement

From: Fabio Gadducci <[email-masked]>
Date: Fri, 01 Oct 1999 18:30:06 +0000

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}