|Funding for:||UK Students, EU Students, International Students|
|Funding amount:||£17,668 p.a. annual stipend|
|Placed On:||6th December 2022|
|Closes:||17th February 2023|
Funding providers: Engineering and Physical Sciences Research Council (EPSRC) and Swansea University's Faculty of Science and Engineering
Subject areas: Computer Science
Comparing the expressiveness of different computation models and formalisms is an important theme in many fields of theoretical computer science including complexity theory, descriptive complexity and automata theory. The main aims of this project would be to carry out such comparisons across classes of functions naturally defined by automata, λ-calculi and logical interpretations, using 0 (probably) techniques coming from automata theory and the semantics of linear logic.
In 1996, a striking connection between λ-calculus and automata was uncovered: the simply-typed functions from strings to Booleans using Church encodings recognize exactly the class of regular languages. This sort of connection was then refined and further exploited by specialists of linear logic and automata to tackle problems related to higher-order model checking and automata running over infinite data.
Following this, there was an effort in recent years to systematically compare the expressive power of Church encodings in linear λ-calculi and string-to-string transductions, unveiling some non-trivial connections including a characterization of regular transductions. The techniques involve a mix of semantic evaluation, analyses of the normal forms in the λ-calculus and non-trivial automata-theoretic results. To get a flavour of both the aims and the methods employed, one may skim through the following:
This project would be a continuation of that effort. There are a number of concrete problems to tackle that can serve as a good introduction to working in that setting, including:
This could be followed-up by investigations in more challenging problems in the same area or into broader concerns specific to one of the domains involved (such as investigations which involving defining well behaved-class of tree transductions or more specialized topics in linear logic such as weak exponentials or quantification over linear types).
Candidates must normally hold an undergraduate degree at 2.1 level in Computer Science, Mathematics or a closely related discipline, or an appropriate master’s degree with a minimum overall grade at ‘Merit’ (or Non-UK equivalent as defined by Swansea University).
English Language requirements: If applicable – IELTS 6.5 overall (with at least 6.0 in each individual component) or Swansea recognised equivalent.
This scholarship is open to candidates of any nationality. There is an International quota for all UKRI funded scholarships. If the quota has been reached by the closing date, please note you may no longer be eligible for this scholarship.
This scholarship covers the full cost of tuition fees and an annual stipend of £17,668.
Additional research expenses will also be available.
Type / Role: