EPSRC logo

Details of Grant 

EPSRC Reference: EP/N033353/1
Title: Special inverse monoids: subgroups, structure, geometry, rewriting systems and the word problem
Principal Investigator: Gray, Dr RD
Other Investigators:
Researcher Co-Investigators:
Project Partners:
City University of New York NOVA University of Lisbon University of Manchester, The
University of Novi Sad University of St Andrews
Department: Mathematics
Organisation: University of East Anglia
Scheme: First Grant - Revised 2009
Starts: 05 July 2016 Ends: 04 July 2018 Value (£): 100,576
EPSRC Research Topic Classifications:
Algebra & Geometry Logic & Combinatorics
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
08 Jun 2016 EPSRC Mathematics Prioritisation Panel Meeting June 2016 Announced
Summary on Grant Application Form
This project is concerned with the study of certain fundamental objects in algebra called groups, monoids and inverse monoids. These objects arise naturally in the mathematical study of symmetry and partial symmetry. Given any mathematical structure on a set, the collection of structure-preserving mappings from the set to itself form a monoid, the collection of all symmetries form a group, while the partial symmetries give rise to an inverse monoid. In this way these algebraic objects pervade mathematics.

One way to represent a group, monoid of inverse monoid is via a presentation. The elements are represented by strings of letters, called words. We are also given a set of pairs of words, called defining relations, which are rules telling us that certain pairs of words are equal to each other. Then two words are defined to be equal if one can be turned into the other by a sequence of applications of the defining relations. For example, using the alphabet with the letters a and b, and just with a single defining relation ab=ba, the words aba and aab are equal since aba = a(ba) = a(ab) = aab. On the other hand, the words bb and ab are not equal since one cannot be transformed into the other using the relation ab=ba.

A famous result in twentieth century mathematics shows that there does not exist, in general, an algorithm to decide whether two words are equal in a monoid defined by a finite presentation. This is known as the word problem, and is also undecidable in general both for finitely presented groups and inverse monoids. These results are important since they were some of the first concrete natural decision problems proven to be undecidable in general. 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 to be major difficulties in investigating the class as a whole.

Given that the word problem is undecidable in general, a lot of research has been done to identify classes of monoids for which the word problem is decidable. One fundamental idea is that by restricting the number of defining relations in the presentation, this should limit the complexity of the object that it defines. An important result of this kind for groups is Magnus's theorem which shows that groups defined by a single defining relation all have decidable word problem. In contrast to this, the following problem remains open:

Open problem. Is the word problem decidable for monoids with a single defining relation?

This important problem has been open for more than half a century, and is one of the main motivations for our research project. Rather than attacking this problem directly, the project instead aims to develop various aspects of the theory of certain inverse monoids, called special inverse monoids. Specifically the project will develop certain important tools from theoretical computer science, from the area of rewriting systems, to investigate the subgroups, structure, and geometry of these inverse monoids. We will then apply this theory to investigate the word problem for these inverse monoids which will then lead to important results about decidability of the word problem, in general, for monoids defined by a single defining relation.

The project will involve 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.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.uea.ac.uk