A Fibred Approach to Rewriting --- How the Duality between Adding and Deleting Cooperates with the Difference between Matching and Rewriting

Wolfram Kahl

Technical Report Nr. 9702, 26 pages
Fakultät für Informatik
Universität der Bundeswehr München
May 1997
(.bib, .ps.gz)


We present a new approach to rewriting obtained by enhancing and unifying existing variants inside the algebraic (or better categorical) approach to (graph) rewriting. Our approach is motivated by second-order term graph rewriting and stresses on one hand the two-step nature of rule application consisting of deleting and adding items and on the other hand the heterogeneous nature of the rewriting setup where rule steps should be clearly distinguished from matching of rule sides into redexes.

Complementing the existing opfibration approach with a dual fibration step turns out to yield a natural and flexible approach with useful new applications. The resulting fibred approach takes advantage of the heterogeneous setting and appropriately reflects the duality between deleting and adding in the course of rewriting, in contrast with the double-pushout approach which simplifies this duality into a symmetry. An important contribution is the universal characterisation of the host object, which has to be found as a pushout-complement in the double pushout approach.

The fibred approach is presented in abstract and independent from any concrete application categories in the manner of High-Level Replacement Systems. Our original motivation for the development of the fibred approach comes from term graphs with bound variables where all other approaches failed; in this paper we present an unusual view on term rewriting as running example.


Wolfram Kahl --- 24 February 1999