Postgraduate

Computability and Constrained Equations in Free Semigroups

Loughborough, United Kingdom
Duration
3 years full-time / 6 years part-time
Subject
Computer Science
IELTS
6.5 overall, no part below 6About the same overall: PTE Academic 55, TOEFL iBT 81, Duolingo English Test 120, Oxford Test of English 136.

At a glance

Summary by AI

Reading the course page…

Written by AI from this page. Your counsellor confirms the details.

Overview

Given a finite set (A), and an associative binary operation (\circ), a semigroup is a set that contains (A) and is closed under (\circ). 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, (\circ) is the concatenation operation, and (A^+) contains all non-empty strings (also called words) comprising symbols from (A).

Show all

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 that 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, algorithms, and complexity. A successful candidate should have 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. Further assessment criteria. The candidate will be part of the theoretical computer science research theme and will work closely with the primary supervisor, supported by regular supervision meetings.

They will likely share an office with other PhD students and postdocs working in a mixture of theoretical and applied areas of computer science. 94% of Loughborough’s research impact is rated world-leading or internationally excellent. REF 2021

Entry requirements

Undergraduate degree in Computer Science or Maths

English language requirements

IELTS6.5 overall, no part below 6

The standard University IELTS English language requirement is 6.5 overall with 6.0 in each individual element (reading, writing, listening and speaking).

Fees

International students: GBP 29,500

UK students: GBP 5,238

Start dates

October 2026, February 2027, July 2027

Application deadline

01 JAN 2027

Campus

  • Loughborough, United Kingdom

If you studied in United States

70 countries

Postgraduate Taught

Academic

GPA 4.0 scale: First-class honours (70%) 3.5, Upper second-class honours (60%) 3, Lower second-class honours (50%) 2.6

English language

The standard University IELTS English language requirements is 6.5 overall with 6.0 in each individual element (reading, writing, listening and speaking). Some degrees may require higher levels English language, these have been clearly stated on the individual degree pages.

List of accepted qualifications Pre-sessional English courses Undergraduate courses Postgraduate degrees Content footer Section footer Branch footer Site footer Global footer Study

From Loughborough University's published requirements for students from United States. Your counsellor confirms what applies to you.

Scholarships at Loughborough University

9 for this level
  • Alumni Bursary10% of fees
  • Alumni Discount
  • Care Leaver's Scholarship
  • Excellence Scholarships

All scholarships at Loughborough University

Plan your first year

Change the figures to your own
TuitionGBP 29,500
Visa application, from outside the UKGBP 558
Health surcharge, first year how it is chargedGBP 776
First year in totalGBP 44,886

The health surcharge is paid for the whole visa when you apply; one year is counted here. Figures as gov.uk showed them on 24 OCT 2026.

After your offer

Your portal tracks each stop
  1. Your offer

    The university sends a conditional or unconditional offer. We follow it until every condition is met.

  2. Accept and pay the deposit

    You accept the offer and pay any deposit the university asks for, by its deadline.

  3. Your CAS

    The university issues your Confirmation of Acceptance for Studies, the number your visa application needs. We help you get it.

  4. Your Student visa

    You apply with your CAS and show GBP 40,039 for your first year: tuition plus living costs. We help you prepare the documents.

East MidlandsEast of EnglandLondonNorth EastNorth WestNorthern IrelandScotlandSouth EastSouth WestWalesWest MidlandsYorkshire and the HumberLoughborough University

Where you will study

Loughborough, East Midlands, United Kingdom

Study in LoughboroughEast Midlands

Year one, for your visa
Tuition
GBP 29,500
Living costs, 9 × GBP 1,171
GBP 10,539
To show for your visa, 9 months
GBP 40,039

UKVI's living-cost figure outside London (GBP 1,529 in London), as gov.uk showed it on 24 OCT 2026. Check gov.uk

Also before you travel: the visa fee, GBP 558, and the health surcharge, GBP 776 for each year of your visa. Plan your first year

Can I get in?

Check my own chances

From United States: GPA 4.0 scale: First-class honours (70%) 3.5, Upper second-class honours (60%) 3, Lower second-class honours (50%) 2.6

Requirements for United States
Who helps you

A counsellor checks your documents before Loughborough University sees them, then stays with you through your offer, CAS and visa.

Similar courses

More like this

Share

TuitionGBP 29,500/yr
Apply