Mark's Research

I work in the School of Mathematics at the University of Manchester, in the north-west of England. I am affiliated to the Algebra Group, the Logic Group, the Tropical Mathematics Group and the Centre for Interdisciplinary Computational and Dynamical Analysis (CICADA).

By original training I'm both a mathematician and a computer scientist and I've worked at various points on the spectrum between the two subjects, but my interests over the last few years have drifted more towards the mathematical end. The main focus of my research is the theory of semigroups and automata, which I view as two aspects of the same subject (an automaton being essentially a semigroup action). However, I spend much of my time working on connections with adjacent fields and application areas, such as combinatorial and geometric group theory, computational complexity, quantum computation, formal language theory, and most recently tropical algebra and geometry.

Some of the major topics on which I have recently worked include:

• Tropical Matrix Semigroups. Matrices over the tropical semiring (the real numbers equipped with operations of addition and maximum) arise naturally in a huge range of application areas, including automata theory, combinatorial optimisation and scheduling, phylogenetics and enumerative algebraic geometry. My aim is to understand the algebraic structure of these matrices under multiplication, which turns out to be very closely bound up with the geometry of tropical convex sets and polytopes. For example, some of our recent research has shown that the von Neumann regular matrices are exactly those whose row space is a polytope of pure dimension equal to row and column rank of the matrix. It follows that almost all of the numerous notions of rank which have been studied for tropical matrices coincide in the case of regular matrices. This research started as part of CICADA and is now funded by EPSRC grant EP/H000801/1. Parts of it are joint work with Christopher Hollings , Zur Izhakian and/or Marianne Johnson .


• Geometry of Finitely Generated Semigroups. It is well known that finitely generated groups admit a natural geometric structure, which encapsulates many important aspects of their algebraic structure. Conventional geometry is ill-equipped to model semigroups in the same way, because a lack of inverses means that the distance between two elements can depend upon the direction of travel. Indeed, the presence of ideals means that elements can even be at finite distance in one direction and "distance infinity" in the other. This research asks: to what extent can geometric methods be used to study semigroups, when one allows "metrics" which are asymmetric and admit distance infinity? We have shown that foundational results of geometric group theory, such as the Svarc-Milnor Lemma, have analogues in this setting, and we are hopeful that more advanced techniques will also transfer. Conversely, it is obvious that "asymmetric" distance spaces arise with great frequency in nature, and hence in applied mathematics. We believe that semigroup-theoretic methods will assist with the study of these spaces, in the same way that group-theoretic methods have been applied in geometry. This project is joint work with Robert Gray .


• Small Overlap Monoids. Small overlap conditions are combinatorial restrictions on finite presentations for monoids, which limit the complexity of derivation sequences between equivalent words. They are the semigroup analogue of the small cancellation conditions used in geometric group theory. Small overlap monoids are the "generic" finitely presented monoids, in the sense that a randomly chosen a-generator, k-relation monoid presentation of size n satisfies any given small overlap condition with probability which converges exponentially fast to 1 as n grows. Recent research has developed a new combinatorial approach to these monoids which seems particularly useful for algorithmic and automata-theoretic purposes, yielding for example a linear time uniform algorithm for the word problem monoids given by C(4) presentations, and an extension of Kleene's theorem to these monoids.