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/category of abstract algebras. In this talk, we will consider algebras of partial functions for a foundational signature. The signature has two 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. 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.

Start Date

Venue

Online Zoom meeting

End Date

Célia Borlido

(FCTUC/CMUC)

Célia Borlido-29Oct2021.pdf412.92 KB

Semigroups, Automata and Languages