I am interested in supervising projects in the following areas: algebras of relations, algebras of functions, algebraic logic, boolean algebra with operators, complexity theory and more generally logic.  Other related areas will also be considered.  Applicants should have some training and fluency with pure mathematics.

 

Algebras of binary relations include Kleene Algebra (KA) and Relation Algebra (RA), among others.

It is known that RA has poor computational behaviour in many ways.  The class of representable RAs (RRA) cannot be axiomatised by finitely many equations, the equational theory is undecidable, the problem of telling whether a finite RA is representable is undecidable,  RRA cannot be defined by any set of equations using just finitely many variables etc., etc.  One problem is to prove that RRA cannot be defined by any first-order theory using only finitely many variables. Game theoretic techniques might help with this.  Another problem is to find a simpler kind of algebra (probably a reduct of RA) that has better computational behaviour (finitely axiomatisable representation class or decidable equational theory, for example) but is still reasonably expressive (so Boolean Algebra is too simple for this).  

On the more practical side,  we need to find efficient algorithms for handling constraints over an RA.

 

Here are some other specific problems (from Relation Algebra by Games, Hirsch and Hodkinson, North-Holland, 2002).  PDF version.  This problem list is taken from our book "Relation Algebra by Games" by Hirsch and Hodkinson (2002) and appears by permission of Elsevier Science.  Single copies only may be downloaded provided these are just for your personal use.