Program Overview

Introduction to the PhD Program in Computability and Constrained Equations in Free Semigroups

The PhD program in Computability and Constrained Equations in Free Semigroups at Loughborough University is a research-focused degree that delves into the theoretical aspects of computer science, particularly in the areas of formal language theory, logic, and algorithms. This program is designed for individuals with a strong background in theoretical computer science and discrete mathematics, who are eager to explore the limits of algorithmic approaches in solving satisfiability problems.

Qualification(s) Available

• PhD

Entry Requirements

• Minimum 2:1 honours degree in Computer Science, Mathematics, or a closely related subject.
• Experience with formal mathematical proofs.

Fees for Entry

• UK fee: £5,006 Full-time degree per annum
• International fee: £28,600 Full-time degree per annum

Duration and Start Date

• Full-time: 3 years
• Start date: October 2025, January 2026, April 2026, July 2026

Application Deadline

• 1 April 2026

Project Reference

• CO/JD-SF2/2025

Location

• Loughborough

Subject Area(s)

• Computer Science

Project Details

Given a finite set A, and an associative binary operation o, a semigroup is a set which contains A and is closed under o. If |A| = n, the free semigroup A+ is a particular example of a semigroup. Often in computer science, A is a set of symbols called letters, o is the concatenation operation, and A+ contains all nonempty strings (also called words) comprising symbols from A. The first order theory of a free semigroup is algorithmically undecidable in general, however satisfiability for first order quantifier-free formulas, including single equations, is well-known to be decidable at least in theory. In practice, developing sufficiently efficient algorithms remains a challenge.

The aim of this project is to study equations or quantifier free first-order formulas in free semigroups which are augmented by additional constraints, for example by restricting the values variables may take to rational subsets of A+ or by placing arithmetic constraints on their lengths, and as a result to better understand the limits of algorithmic approaches in solving the resulting satisfiability problems. Such problems have implications in a variety of areas of mathematics and computer science, including formal methods, combinatorial group theory, arithmetic and number theory, formal language theory, theory of computation and combinatorics on words.

The project will consist primarily of producing novel definitions, theorems and proofs, and may include some practical (programming) elements depending on the strengths and interests of a successful applicant. In all cases, a strong background in theoretical computer science and discrete mathematics is required, particularly in topics such as formal language theory, logic and algorithms and complexity.

A successful candidate should have a strong internal motivation and should enjoy problem solving and abstract thinking. They should work well individually, although there will also be opportunities for collaboration and networking both locally and internationally. Good communication skills, both verbal and written, and experience in reading and writing formal mathematics (including proofs) are also desirable. Applicants from diverse backgrounds are strongly encouraged.

Supervisors

• Primary supervisor: Joel Day

English Language Requirements

Applicants must meet the minimum English language requirements. Further details are available on the International website.

Fees and Funding

Tuition fees cover the cost of your teaching, assessment and operating University facilities such as the library, IT equipment and other support services. University fees and charges can be paid in advance and there are several methods of payment, including online payments and payment by instalment. Fees are reviewed annually and are likely to increase to take into account inflationary pressures.

How to Apply

All applications should be made online. Under programme name, select Computer Science. Please quote the advertised reference number: CO/JD-SF2/2025 in your application.

To avoid delays in processing your application, please ensure that you submit a CV and the minimum supporting documents.

The following selection criteria will be used by academic schools to help them make a decision on your application. Please note that this criteria is used for both funded and self-funded projects.

Please note, applications for this project are considered on an ongoing basis once submitted and the project may be withdrawn prior to the application deadline, if a suitable candidate is chosen for the project.