Determinisation of Relational Substitutions in Ordered Categories with Domain

Wolfram Kahl

pp. 243–258 in R. Berghammer, B. Möller, G. Struth (eds.) Relations and Kleene Algebra in Computer Science, RelMiCS/AKA 2008, Frauenwörth, Germany, April 7–11, 2008, LNCS 4988, Springer-Verlag, 2006.

(.bib)

Abstract

We present two different relational generalisations of substitutions, show that they both produce locally ordered categories with domain, and then develop the single-morphism “determiniser” concept that relies only on this framework, while still corresponding to conventional two-morphism unification in both examples. Central to this development is the determinacy concept of “characterisation by domain” introduced by Desharnais and Möller for Kleene algebras with domain; this is here applied in the weakest possible setting.


Wolfram Kahl