Representations in Algebraic Logic

Lead Research Organisation: University College London
Department Name: Computer Science

Abstract

Boole's extensive and successful exploration in algebras of unary relations [2] (nowadays referred to as Boolean Algebras) have proven to have a wide range of applications in computer science. As an extension of this concept, DeMorgan proposed considering such algebras with higher arities [3], which eventually led to Tarski formalising the class of representable algebras of binary relations (RRA) [17]. This opened a wide range of problems in exploring how different signatures of algebraic structures can be represented Boole's extensive and successful exploration in algebras of unary relations [2] (nowadays referred to as Boolean Algebras) have proven to have a wide range of applications in computer science. As an extension of this concept, De Morgan proposed considering such algebras with higher arities [3], which eventually led to Tarski formalising the class of representable algebras of binary relations (RRA) [17]. This opened a wide range of problems in exploring how different signatures of algebraic structures can be represented as algebras of binary relations.
These have also found a number of applications in computer science, from program verification and termination [4, 5] to regular expression equivalence [12]. This is why it is important to keep on exploring the theoretical field of representations to show these structures as concrete algebras in RRA to provide a more intuitive understanding and reasoning about them.

This project will focus on the computational aspects of working with relation algebra. For the full signature of relation algebra, many negative results are known - the equational theory is undecidable, the class RRA has no finite axiomatisation, the problem of determining whether a finite RA has a representation is undecidable, finite RAs can be representable but have no representations over a finite base set (i.e. RA fails to have the finite representation property (FRP)). A key topic in this project will be to consider the computational behaviour of subsignatures of relation algebra, where only some of the RA operators are included.

Specific questions to be solved include, but are not limited to, the following. (i) Which subsignatures of relation algebra have the finite representation property? (ii) For which subsignatures of RA is the representation class finitely axiomatisable? (iii). For subsignatures with decidable decision problems, what is the complexity?

The approach will be based on Hirsch-Hodkinson representation games, the novelty will be to adapt these games to the appropriate signature. A further novelty that will be required, is to modify the games so as to characterise finite representations.
as algebras of binary relations.
These have also found a number of applications in computer science, from program verification and termination [4, 5] to regular expression equivalence [12]. This is why it is important to keep on exploring the theoretical field of representations to show these structures as concrete algebras in RRA to provide a more intuitive understanding and reasoning about them.

Publications

10 25 50

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/S021566/1 01/04/2019 30/09/2027
2251002 Studentship EP/S021566/1 23/09/2019 22/09/2023 Jas Semrl