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

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..