Back to search results

PhD Studentship: Fully Funded EPSRC and Swansea University PhD Scholarship: Comparing the Expressiveness of Transducers and Simply-typed Linear Calculi

Swansea University - Computer Science

Qualification Type: PhD
Location: Swansea
Funding for: UK Students, EU Students, International Students
Funding amount: £16,062 p.a.
Hours: Full Time
Placed On: 17th August 2022
Closes: 28th October 2022
Reference: RS152

Funding providers: Engineering and Physical Sciences Research Council (EPSRC) and Swansea University's Faculty of Science and Engineering

Subject areas: Computer Science

Project description: 

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:

  • comparing the expressiveness of the non-commutative linear λ-calculus and first-order transducers
  • designing minimalistic typed programming languages capturing what is achievable in the linear λ-calculus with Church encodings in the spirit of Bojańczyk’s work on polyregular functions, but for comparison-free polyregular functions
  • carrying out a similar comparison for transducers over infinite structures and functions λ-definable using the Church encoding of coinductive datatypes
  • checking whether there is difference in expressiveness if we allow the full power of classical linear logic instead of the intuitionistic fragment

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).

Eligibility

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.

Additional Funding Information

This scholarship covers the full cost of tuition fees and an annual stipend of £16,062.

Additional research expenses will also be available.

We value your feedback on the quality of our adverts. If you have a comment to make about the overall quality of this advert, or its categorisation then please send us your feedback
Advert information

Type / Role:

Subject Area(s):

Location(s):

PhD tools
 

PhD Alert Created

Job Alert Created

Your PhD alert has been successfully created for this search.

Your job alert has been successfully created for this search.

Ok Ok

PhD Alert Created

Job Alert Created

Your PhD alert has been successfully created for this search.

Your job alert has been successfully created for this search.

Manage your job alerts Manage your job alerts

Account Verification Missing

In order to create multiple job alerts, you must first verify your email address to complete your account creation

Request verification email Request verification email

jobs.ac.uk Account Required

In order to create multiple alerts, you must create a jobs.ac.uk jobseeker account

Create Account Create Account

Alert Creation Failed

Unfortunately, your account is currently blocked. Please login to unblock your account.

Email Address Blocked

We received a delivery failure message when attempting to send you an email and therefore your email address has been blocked. You will not receive job alerts until your email address is unblocked. To do so, please choose from one of the two options below.

Max Alerts Reached

A maximum of 5 Job Alerts can be created against your account. Please remove an existing alert in order to create this new Job Alert

Manage your job alerts Manage your job alerts

Creation Failed

Unfortunately, your alert was not created at this time. Please try again.

Ok Ok

Create PhD Alert

Create Job Alert

When you create this PhD alert we will email you a selection of PhDs matching your criteria.When you create this job alert we will email you a selection of jobs matching your criteria. Our Terms and Conditions and Privacy Policy apply to this service. Any personal data you provide in setting up this alert is processed in accordance with our Privacy Notice

Create PhD Alert

Create Job Alert

When you create this PhD alert we will email you a selection of PhDs matching your criteria.When you create this job alert we will email you a selection of jobs matching your criteria. Our Terms and Conditions and Privacy Policy apply to this service. Any personal data you provide in setting up this alert is processed in accordance with our Privacy Notice

 
 
 
More PhDs from Swansea University

Show all PhDs for this organisation …

More PhDs like this
Join in and follow us

Browser Upgrade Recommended

jobs.ac.uk has been optimised for the latest browsers.

For the best user experience, we recommend viewing jobs.ac.uk on one of the following:

Google Chrome Firefox Microsoft Edge