A Boolean matrix is a matrix with elements from the Boolean semiring ({0, 1}, +, x), where the addition and multiplication are as usual with the exception that 1 + 1 = 1. In this thesis we study eight classes of monoids whose elements are Boolean matrices. Green's relations are five equivalence relations and three preorders which are defined on an arbitrary monoid M and describe much of its structure. In the monoids we consider the equivalence relations are uninteresting  and in most cases completely trivial  but the preorders are not and play a vital part in understanding the structure of the monoids. Each of the three preorders in each of the eight classes of monoids can be viewed as a computational decision problem: given two elements of the monoid, are they related by the preorder? The main focus of this thesis is determining the computational complexity of each of these twentyfour decision problems, which we successfully do for all but one.
Date of Award  31 Dec 2018 

Original language  English 

Awarding Institution   The University of Manchester


Supervisor  Marianne Johnson (Supervisor) & Mark Kambites (Supervisor) 

 semigroup theory
 computational complexity
 Boolean matrices
Some algorithmic problems in monoids of Boolean matrices
Fenner, P. (Author). 31 Dec 2018
Student thesis: Phd