Formal languages and models of computation (Ref: CO/LP-SF1/2026)

The area of formal language and automata theory focuses on the investigation of abstract machines, and it is particularly interested in what problems these devices can solve and what resources they use. The importance of these formalisms is fundamental in theoretical computer science as their utility has been found in many areas, like compiler construction, text manipulation, and formal verification, and it is related to their capability of representing (potentially) infinite sets using finite representations. Their theoretical as well as practical importance motivates the investigation on how to obtain optimised implementations. In this setting, it is important to keep their representations- their algorithms and the resources they use -as much succint and limited as possible, depending on the specific characteristics of the devices under consideration.

This project will span from the study of these models and their computations to the investigations of the complexity their algorithms, exploring techniques and tools from the area of formal langue theory. The goal is to expand the knowledge in this branch of theoretical computer science, in order to improve the understanding of different models of computations operating under resource restrictions, and to develop theories and techniques to study these devices.

Name of primary supervisor/CDT lead:
Luca Prigioniero l.prigioniero@lboro.ac.uk
https://www.lboro.ac.uk/departments/compsci/staff/luca-prigioniero/

Entry requirements:
Applicants should have, or expect to achieve, a first class Honours degree (or equivalent) in a computer science-related degree.
The project will consist primarily of formal mathematics (producing novel definitions, theorems and proofs) and may include some practical (programming) elements. The exact choice of problems and techniques can be tailored to suit the strengths and interests of the candidate.
A successful candidate should have a strong internal motivation and should enjoy problem solving, abstract thinking. They should work well individually, although there will also be opportunities for collaboration and networking both locally and internationally. Good communication skills are also desirable, but there will also be chances to develop these throughout the project. Applicants from diverse backgrounds are strongly encouraged.
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 (typically every 1-2 weeks and at least once per month). They will likely share an office with other PhD students and postdocs working in a mixture related and unrelated areas.
Prospective applicants are welcome to get in touch with the primary supervisor if they have any questions or would like to further discuss the research topics, supervision arrangements, expectations, etc.

English language requirements:
Applicants must meet the minimum English language requirements. Further details are available on the International website (http://www.lboro.ac.uk/international/applicants/english/).

Bench fees required: No

Closing date of advert: 31st July 2026

Start date: October 2026

Full-time/part-time availability: Full-time 3 years

Fee band: Band RB - UK: £5,006; International: £28,600

How to apply:
All applications should be made online. Under programme name, select Computer Science. Please quote the advertised reference number: CO/LP-SF1/2026 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 selffunded 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

Project search terms:
computer science, formal languages, automata theory, theoretical computer science, models of computation

Email Address Sci:
sci-pgr@lboro.ac.uk