Speaker: Célia Borlido, Centro de Matemática da Universidade de Coimbra

Date: 19 April, 14h30

Venue: Lab 2(room 3.74), Department of Mathematics

 Online: https://videoconf-colibri.zoom.us/j/93344876599?pwd=ejkrZ3FpYkh0NE1YV3NCdGFMOGw3QT09

Title: Algebras of partial functions for a foundational signature 

Abstract: The study of algebras of partial functions is an active area of research that investigates collections of partial functions and their interrelationships from an algebraic perspective. The partial functions are treated as abstract elements that may be combined algebraically using various natural operations. In pure mathematics, algebras of partial functions arise naturally as structures such as inverse semigroups, pseudogroups, and skew lattices. In theoretical computer science, they appear in the theories of finite state transducers, computable functions, deterministic propositional dynamic logics, and separation logic. Many different selections of operations have been considered, each leading to a different class of abstract algebras. In this talk, we will consider algebras of partial functions for the signature consisting of two foundational operations, both binary: the standard set-theoretic relative complement operation and a domain restriction operation. We will investigate the representation and complete representation classes for such algebras, and provide a finite equational axiomatization for the class of algebras representable by partial functions over the chosen signature. We will also see that the class of completely representable algebras admits a universal-existential-universal axiomatization, which is the simplest possible, in the sense that no existential-universal-existential axiomatisation exists. This is based on joint work with Brett McLean.