Five PhD studentships in Theoretical Computer Science, Kent (U.K.), Deadline:

Funding is available for the following five PhD studentships within the TCS group at the University of Kent. Applicants should contact the project supervisor directly for further details.

Project Supervisor: Dr Eerke Boiten (E.A.Boiten at kent.ac.uk)
Project Title: Reasoning about Scratch Cards

Scratch cards are used widely in lotteries and games, and recently also in e-voting protocols. However, public confidence in e-voting is very low. This research project can make a difference by developing mathematical and logical abstractions of scratch cards that allow formal reasoning, and consequently watertight proofs of the security of protocols using them. This would be a great project if you are interested in practical symbolic reasoning; knowledge of security, cryptography, formal methods, probability, or logics would be a bonus.

Project Supervisor: Dr Olaf Chitil (O.Chitil at kent.ac.uk)
Project Title: Tracing Functional Programs with Hat

Hat (www.haskell.org/hat) is a sophisticated tool for locating faults in Haskell programs. Hat consists of a trace generation system plus various tools for viewing a trace. The aim of the research project is to improve Hat by both extending it and easing its application in practise: (1) Apply several theoretical results of a recent EPSRC project on tracing in Hat (e.g. algorithmic debugging with functions as finite maps). (2) Integrate the trace generator of Hat into the byte code interpreter of the Glasgow Haskell system (GHC). (3) Enable traced code to call and be called from unmodified non-tracing code, such that Hat can use pre-compiled libraries of GHC.

Project Title: The Essence of Transfinite Reductions
Project Supervisor: Dr Stefan Kahrs (S.M.Kahrs at kent.ac.uk)

Infinitary Rewriting is an area of Term Rewriting in which research has studied infinitary terms and infinitary reductions. While the notion of infinitary terms is fairly settled, the existing notions of infinitary reduction leave a lot to be desired - the definitions are suspiciously complicated, the established results less than impressive. Thus, there appears to be a lot of room for improvement. There are different angles that are worth exploring. Firstly, there are several alternative ways to define transfinite reductions. Secondly, one would hope that some of these alternative ways lead to good properties of transfinite reduction. Thirdly, it is not even a priori clear what would constitute such a good property.

Project Title: Finding Security Bugs in x86 code
Project Supervisor: Dr Andy King (A.M.King at kent.ac.uk)

The project will investigate how security vulnerabilities can be automatically located in x86 code. Rather than trap a fault when it occurs as the program is running, the project will devise compile-time techniques for locating faults before the program is executed. The project will apply techniques from compiling, constraint solving and semantics, though the applicant need not have expertise in all these fields.

Project Title: Refactoring Proofs
Project Supervisor: Prof Simon Thompson (S.J.Thompson at kent.ac.uk)

Refactoring allows the programmer to modify the design or structure of a program without changing its behaviour. Recent work in the Functional Programming group at Kent has developed refactoring systems for Haskell 98 (HaRe) and Erlang (Wrangler). Programming and proof have much in common, and indeed under the "propositions as types" analogy, they are different views of the same objects. The aim of this project is to explore how refactoring can be incorporated into proof development systems, and will combine theoretical work, implementation and usability analysis to ensure that the results will be of value to users of proof assistants. The aim of this project is to investigate refactoring for proofs.