Categorical Rewriting

We believe that rewriting needs a semantics at an intermediate level of abstraction between the syntax and the relational model. Originally it was hoped that 2-categories would provide such a model but despite some one-off results, 2-categorical models of TRSs have failed to make a lasting impact. Our research focuses on applying the theory of enriched monads to term rewriting with very promising results. These monads have been used to give semantic proofs of some difficult results in modular term rewriting. We are currently using monads to tackle open problems in modular term rewriting for conditional TRSs and unions which permit limited sharing.

Journal Papers

• An Introduction to Categorical Rewriting N. Ghani and C. Lueth. Submitted to Journal of Universal Computing Structures

Research Papers

• Compositional Term Rewriting: An Algebraic Proof of Toyama's Theorem. . C. Lueth. Published in proceedings of Rewriting Techniques and Applications 1996 number 1103 in in Lecture Notes in Computer Science. Springer-Verlag 1996.

• Monads and Modular Term Rewriting . N.Ghani and C.Lueth. Published in proceedings of Category Theory and Computer Science 1997 , number 1290 in Lecture Notes in Computer Science, pages 69-86. Springer-Verlag 1997.

• Rewriting the Conditions in Conditional Rewriting . N.Ghani and C.Lueth. Published as Technical Report 2000/20, Department of Maths and Computer Science, University of Leicester 2000.

Back to the homepage.