31/01/2008
Vincent van Oostrom (Université d'Utrecht)
From sorting via braids, self-distributivity, and the substitution lemma of the lambda-calculus, to multisets

We associate rewrite relations associated to the four systems in the title, show how they are related, and how techniques from rewriting can be used to establish properties. In particular:

• random descent, for optimality;
• decreasing diagrams, for confluence;
• residual systems, for orthogonality; and
• commutative residual algebras, for multisets.