Research Projects



Special inverse monoids: subgroups, structure, geometry, rewriting systems and the word problem
(EPSRC grant EP/N033353/1, July 2016-July 2018)

Algorithmic problems in algebra have their origins in problems in logic and topology investigated in the beginning of the 20th century by Thue (1914), Tietze (1912), and Dehn (1912). This work shows how the problems of decidability of relations in Thue systems, the homeomorphism problem for topological manifolds, and the homotopy equivalence problem in finite dimensional manifolds, are equivalent to certain algebraic problems, specifically the word problem for finitely presented semigroups and groups, and the isomorphism and conjugacy problems for finitely presented groups. Since then the subject has developed into what is now a highly active and exciting area of research, which provides a meeting point for ideas from logic, algebra and theoretical computer science.

One of the most fundamental and important algorithmic problems in algebra is the word problem. Recall that an algebraic structure (e.g. a group, semigroup, associative algebra or Lie algebra) presented by a set of generators $X$ and defining relations is said to have decidable word problem if there exists an algorithm which, for any pair of terms over the alphabet $X$, tells us whether they represent the same element. The importance of the word problem is clear: decidability of the word problem for a class of algebras indicates that we have some hope of studying the structural properties of algebras in the class, while undecidability of the word problem would suggest there would likely be major difficulties in investigating the class as a whole.

Markov (1947) and Post (1947) proved independently that the word problem for finitely presented monoids is undecidable in general. This result was extended by Turing (1950) to cancellative semigroups, and then by Novikov (1955) and Boone (1958) to groups. Given that the word problem is undecidable in general, a central theme running through the development of combinatorial and geometric group and semigroup theory over the last sixty years has been to identify and study classes of finitely presented groups and semigroups all of whose members have solvable word problem. Important examples include commutative semigroups, hyperbolic groups (in the sense of Gromov), word hyperbolic semigroups, and groups and semigroups that are automatic, admit presentations by finite complete rewriting systems, or satisfy certain small overlap conditions.

One of the most interesting classes of groups that has arisen in this context is that of one-relator groups, that is, groups defined by a finite presentation with a single defining relator. In 1932 Magnus developed a powerful general approach to one-relator groups, now known as the Magnus break-down procedure, which he used to prove several important results about arbitrary one-relator groups, including the Freiheitssatz, and decidability of the word problem. One key tool in Magnus's method is the Reidemeister-Schreier rewriting process for rewriting a presentation of a group to obtain a presentation for a subgroup. He uses this method to give structural information about one-relator groups, showing how any such group can be built up from cyclic groups, in an elegant and intricate way, by repeatedly forming amalgamated products. While this does give a solution to the word problem, the decision algorithm is complicated and its time complexity is unknown.

Since Magnus's groundbreaking work, many other important results about one-relator groups have been proved, including on: the conjugacy and isomorphism problems, hyperbolicity, residual finiteness and solvability, hopficity, automaticity, and cohomology.

Given how much combinatorial algebra has developed over the past sixty years, it is quite striking that the following problem remains open:

Open problem. Is the word problem decidable for one-relation monoids $\mathrm{Mon}\langle A \:|\: u=v \rangle$?

This is widely regarded as one of the most important longstanding open problems in the area. The problem has received significant attention, and a number of special cases have been solved. Adjan (1966) proved that the word problem for $\mathrm{Mon}\langle A \:|\: u=v \rangle$ is decidable if one of the words $u$ or $v$ is empty, or if they are both non-empty and have different initial and different terminal letters. For each of these particular cases, Adjan showed how to reduce decidability of the word problem to solving the word problem for an associated one-relator group, and then appealed to Magnus's result for one-relator groups. Adjan and Oganessian (1987) showed that the word problem in general can be reduced just to considering presentations of the form ${\rm Mon} \langle A \; | \; bsa=cta \rangle $ where $a,b,c \in A$, $b \neq c$ and $s, t \in A^*$. All such monoids are known to be left cancellative. Other important results on one-relation monoids include results on: residual finiteness, the isomorphism problem, conjugacy problem, finite derivation type ($\mathrm{FDT}$), and the Freiheitssatz.

Since Adjan's work, two of the most important contributions to the problem may be found firstly in the work on Zhang on special monoid presentations, and secondly in the work of Ivanov, Margolis and Meakin, on inverse monoid presentations.

Zhang (1991), (1992) showed how any presentation of the form $\mathrm{Mon}\langle A \:|\: w_1=1, \ldots, w_k=1 \rangle$ (so-called, special monoids) can be rewritten to give a finite presentation for its group of units $G$. Using the theory of noetherian confluent string rewriting systems, he showed that in this situation $M$ has decidable word problem if and only if $G$ has decidable word problem. In the particular case that $M$ is one-relator, one obtains a one-relator presentation for $G$, and hence applying Magnus it follows that $M$ has decidable word problem. In this way, Zhang's work both generalises, and provides a new more elegant proof of, Adjan's theorem that special one-relator monoids have decidable word problem.

Ivanov, Margolis and Meakin (2001) give an entirely new approach to the word problem for one-relation monoids via the theory of inverse monoid presentations. The study of algorithmic problems in inverse semigroups goes back to work of Scheiblich (1973) and Munn (1974) who showed how one can use birooted edge-labelled trees (Munn trees) to represent elements of the free inverse monoid. This work was extended by Stephen who used Schutzenberger graphs to study presentations of inverse semigroups. Utilising Adyan (1987), Ivanov, Margolis and Meakin (2001) made the crucial and fundamental observation that a positive solution to the word problem for one-relator special inverse monoid presentations ${\rm Inv} \langle A \; | \; w=1 \rangle$ would imply a positive solution to the word problem for one-relation monoids $\mathrm{Mon}\langle A \:|\: u=v \rangle$. This important result translates the question of decidability of the word problem for arbitrary one-relation monoids into the the realm of inverse monoids---a key step, since inverse monoids are a class that lie closer to groups than arbitrary monoids, and for groups the word problem has been solved. The word problem for one-relator special inverse monoids has been solved in some particular cases, including the case that $w$ is an idempotent.

While Reidemeister-Schreier-rewriting methods are of fundamental importance in the Magnus break-down procedure described above, no attempt has yet been made to use semigroup-theoretic -rewriting methods to investigate the corresponding problems for monoids and inverse monoids. A central theme of the current research project will be to use Reidemeister-Schreier-rewriting methods, and string rewriting systems, to carry out a comprehensive investigation of the class of special inverse monoids with the ultimate aim of making further progress towards the question of decidability of the word problem for one-relation monoids.

Various aspect of one-relation monoids, and inverse monids, will be investigated in the project. Including:

I) Subgroups of special inverse monoids

Developing RS-rewriting methods to study the units (right units, and other maximal subgroups) of special inverse monoids.

II) Rewriting systems and the word problem

To develop a theory of convergent rewriting systems which operate on Munn trees, and apply it to relate decidability of the word problem of the special inverse monoid $M$ and its group of units $G$.

III) Directed geometry

Investigate the directed geometry of the one-relation left-cancellative monoids, and the directed geometry of the Schutzenberger graphs, and groups, of special one-relator inverse monoids.

IV) Homological finiteness properties

Investiage the question of whether every one-relation monoid admits a presentation by a finite complete rewriting system, and closely related to this the question of whether every such monoid is of homological type left- and right-FP infinity?

The project involes extensive collaboration with researchers both from the UK and from universities in Portugal, Serbia and the USA. We will organise a workshop midway through the project, centred around its main themes, which will bring together leading experts from a diverse range of topics in algebra, logic and theoretical computer science.