	Department of Mathematics & Computer Science

Next: Further work, questions Up: paper10 Previous: Example of a GAP

Applications

MacLane wrote that ``the notion of Kan extensions subsumes all the other fundamental concepts of category theory'' in section 10.7 of [12] (entitled ``All Concepts are Kan Extensions''). So the power of rewriting theory may now be brought to bear on a much wider range of combinatorial enumeration problems. Traditionally rewriting is used for solving the word problem for monoids. It has also been used for coset enumeration problems [15,10]. It may now also be used in the specification of

i): equivalence classes and equivariant equivalence classes,
ii): arrows of a category or groupoid,
iii): right congruence classes given by a relation on a monoid,
iv): orbits of an action of a group or monoid.
v): conjugacy classes of a group,
vi): coequalisers, pushouts and colimits of sets,
vii): induced permutation representations of a group or monoid.

and many others. In this paper we are concerned with the description of the theory and the implementation of the procedure with respect to one ordering. It is hoped to consider implementation of efficiency strategies and other orderings on another occasion. The advantages of our abstraction should then become even clearer, since one efficient implementation will be able to apply to a variety of situations, including some not yet apparent.

Next: Further work, questions Up: paper10 Previous: Example of a GAP

Author: A. Heyworth, tel: +44 (0)116 252 3884
Last updated: 2000-11-24
MCS Web Maintainer
This document has been approved by the Head of Department.
© University of Leicester.

Department of Mathematics & Computer Science

Applications