LFCS Theory Seminar
Room 2511, JCMB, King's Buildings
4pm, Tuesday 28th October 1997

Title: Conditional Term Rewriting Systems Via Enriched Monads

Speaker: Neil Ghani (University of Birmingham)

Monads can be used to give a syntax-free presentation of algebraic theories such as monoids, groups etc. Infact, by enriching the theory many of the structures of use in category theory (SMC's, SMCC's, CCC's etc, w-CPO's) can also be seen as algebraic theories. Using this general framework, I will show that term rewriting systems are also algebraic and then ask the same question of conditional term rewriting systems.

A priori the answer should be no as CTRSs have the feel of essentially algebraic theories. However, I shall show that we can get around this problem by using a base category of algebras in which the conditions of a CTRS can be interpreted. I shall conclude by discussing the obstactles to applying this observation to problems in modular rewriting.

This is joint work with Stefan Kahrs and Christoph Lueth