Override and restricted union for partial functions

Abstract

The {\em override} operation $\bigsqcup$ is a natural one in computer science, and has connections with other areas of mathematics such as hyperplane arrangements. For arbitrary functions $f$ and $g$, $f\bigsqcup g$ is the function with domain $dom(f)\cup dom(g)$ that agrees with $f$ on $dom(f)$ and with $g$ on $dom(g)\backslash dom(f)$. Jackson and the author have shown that there is no finite axiomatisation of algebras of functions of signature $(\bigsqcup )$. But adding operations (such as {\em update}) to this minimal signature can lead to finite axiomatisations. For the functional signature $(\bigsqcup ,\backslash )$ where $\backslash$ is set-theoretic difference, Cirulis has given a finite equational axiomatisation as subtraction o-semilattices. Define $f⋎g=(f\bigsqcup g)\cap (g\bigsqcup f)$ for all functions $f$ and $g$; this is the largest domain restriction of the binary relation $f\cup g$ that gives a partial function. Now $f\cap g=f\backslash (f\backslash g)$ and $f\bigsqcup g=f⋎(f⋎g)$ for all functions $f,g$, so the signatures $(⋎)$ and $(\bigsqcup ,\cap )$ are both intermediate between $(\bigsqcup )$ and $(\bigsqcup ,\backslash )$ in expressive power. We show that each is finitely axiomatised, with the former giving a proper quasivariety and the latter the variety of associative distributive o-semilattices in the sense of Cirulis.