Close icon

Personalise what you see on this page.

Choose from the options below. We'll show you information based on your current location as default.

I'M FROM

  • United States
Please select so we can show the most relevant content.

LIVING IN

  • United States
Please select so we can show the most relevant content.

LOOKING FOR

  • Postgraduate courses
Please select so we can show the most relevant content.
Viewing as a student from United States living in United States interested in Postgraduate courses

Computability and Constrained Equations in Free Semigroups - PHD

Loughborough University

Add to favourites
Loughborough University

Course options

4 options available

  • Qualification

    PhD/DPhil - Doctor of Philosophy

  • Location

    Loughborough University

  • Study mode

    Full time

  • Start date

    OCT

  • Duration

    3 Years

Course summary

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.

Tuition fees

Students living in United States
(International fees)

£ 28,600per year

Tuition fees shown are for indicative purposes and may vary. Please check with the institution for most up to date details.

University information

Loughborough University

Loughborough University

Loughborough University

  • University League Table

    7th

  • Campus address

    Loughborough University, Epinal Way, Loughborough, Leicestershire, LE11 3TU, United Kingdom

VIEW PROFILE
The university's two campuses are located in Loughborough and London, both close to airports, making it easy to explore Europe and beyond.
Loughborough's research community has over 1,200 research students spanning 90 nationalities, with more than 800 members of staff supporting them.
Home to over 18,000 students and staff from more than 130 different countries. Of the students based at the London campus, 80% are international students.

Subject rankings

  • Subject ranking

    Marketing

    10th out of 90

  • Entry standards

    / Max 211
    155 73%

    12th

  • Graduate prospects

    / Max 100
    n/a

  • Student satisfaction

    / Max 4
    2.92 73%

    83rd

    1

Is this page useful?

Yes No

Sorry about that...

HOW CAN WE IMPROVE IT?

SUBMIT

Thanks for your feedback!