Modal restriction semigroups: towards an algebra of functions

Abstract

Restriction semigroups model algebras of partial maps under composition and domain. Here we consider restriction semigroups for which the usual Boolean operations on domains are modeled. Such algebras are capable of modeling the usual modal operators considered in dynamic logic. Indeed adding a natural functional variant of union to the signature gives a deterministic version of the modal semirings of Möller and Struth, but also a monoidal version of the classical restriction categories of Cockett and Manes. Other operations modeled are intersection and (in the finite case) functional iteration. In each case, axiomatizations of the concrete functional examples are given, leading to algebraic models of partial maps incorporating all the domain-related and set-theoretic operations previously considered. Our algebras furnish natural algebraic semantics for the logics of deterministic computer programs, leading to new results for some variants of propositional dynamic logic.