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 pre-orders 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 pre-orders are not and play a vital part in understanding the structure of the monoids. Each of the three pre-orders 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 pre-order? The main focus of this thesis is determining the computational complexity of each of these twenty-four decision problems, which we successfully do for all but one.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:756874 |
| Date | January 2018 |
| Creators | Fenner, Peter |
| Contributors | Kambites, Mark |
| Publisher | University of Manchester |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | https://www.research.manchester.ac.uk/portal/en/theses/some-algorithmic-problems-in-monoids-of-boolean-matrices(d9cc2975-fa24-42c9-8505-5accaaa2a73e).html |
Page generated in 0.1816 seconds