Formal languages and models of computation (Ref: SCI25-LP)

Formal language and automata theory studies abstract machines, focusing on the problems they solve and the resources they require. These formalisms are fundamental to computer science, with applications in areas like compiler construction, text manipulation, and formal verification. Despite their finite representations, these devices can represent potentially infinite sets, making them both theoretically and practically important. Research aims to optimise their implementations, ensuring that their representations — algorithms and resource usage — are as concise and efficient as possible, tailored to the characteristics of the devices. 

This project will study these models and their computations, and will investigate the complexity of their algorithms, using techniques and tools from the field of formal language theory. The goal is to advance knowledge in this area of theoretical computer science, improve our understanding of different models of computation operating under resource constraints, and develop new theories and techniques to study these devices.

The project focuses on theoretical computer science, including developing new definitions, theorems, and proofs, with potential programming elements. The specific problems can be tailored to the candidate’s strengths and interests.

The candidate should be self-motivated, problem-solving minded, and able to work independently, though collaborations are available locally and internationally. Strong communication skills are desirable, with ample opportunities to develop them. Applicants from diverse backgrounds are encouraged to apply.

The candidate will join the TCS research theme, working with the supervisor, receiving regular support, and gaining skills in publication writing and conference presentation. Travel opportunities are available. 

Prospective applicants are encouraged to contact the primary supervisor to discuss research topics and expectations.

Supervisor:

• Luca Prigioniero

Entry requirements:

Applicants should have, or expect to achieve, a First-Class Honours degree (or equivalent) in a computer science/mathematics-related degree.

English language requirements:

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

Funding information:

The studentship is for 3 years full-time equivalent and provides a tax-free stipend of £19,237 per annum for the duration of the studentship plus university tuition fees.

Please note that studentships will be awarded on a competitive basis to applicants who have applied to this project and other advertised projects starting with advert reference ‘SCI25-’ in the School of Science. Successful candidates will be informed during April 2025.

How to Apply:

All applications should be made online. Under programme name, select ‘Computer Science’. Please quote the advertised reference number: ‘SCI25-LP’ 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.

Project search terms:

• computer science
• formal language theory
• automata theory
• descriptional complexity
• models of computation
• computational complexity
• complexity theory
• computability theory
• theoretical computer science

Email Address:

[email protected]