Mobile menu icon
Skip to navigation | Skip to main content | Skip to footer
Mobile menu icon Search iconSearch
Search type

Department of Computer Science

Computational logic: adventures with the fluted fragment

Primary supervisor

Additional information

Contact admissions office

Other projects with the same supervisor


  • Competition Funded Project (Students Worldwide)

This research project is one of a number of projects at this institution. It is in competition for funding with one or more of these projects. Usually the project which receives the best applicant will be awarded the funding. Applications for this project are welcome from suitably qualified candidates worldwide. Funding may only be available to a limited set of nationalities and you should read the full department and project details for further information.

Project description

Many problems in computational logic reduce to the satisfiability problem: given a formula of some logic, determine whether that formula is satisfiable (i.e., represents a logically possible situation). It is well known that, for first-order logic as a whole, this problem is undecidable; however, for various fragments of first-order logic, it admits of an algorithmic solution. One such fragment is the fluted fragment, which originated in the work of W. Quine in the 1960s, and which in recent years has attracted renewed interest. Unlike many decidable fragments---in particular, the vast majority of so-called description logics---the fluted fragment is not limited in the number of variables or the arity of the predicates appearing in its formulas. Much is known about its computational properties: thus, for example, the satisfiability problem for its m-variable sub-fragment is in (m-2)-NExpTime (for m > 2) and is m/2-NExpTime hard (for even m > 1). Very recently, two extensions of the fluted fragment have been shown to be decidable: one with counting quantifiers, the other with a single transitive relation.

Yet many questions remain. For instance, it has not yet been possible to close the complexity gap mentioned in the previous paragraph. The extensions with counting quantifiers are still poorly understood (and only weak complexity results are available). It is not known whether satisfiability for fluted logic with two transitive relations (but without equality) is decidable. And the same holds for the extension with both counting quantifiers and a single transitive relation. The aim of this project is to resolve as many of these issues as possible, and, additionally, to forge links with fragments of first-order logic, notably, description logics, which have been developed with a more application-oriented agenda in mind. The research may be taken in either a purely theoretical direction, or via a mixture of theory and implementation.

The project requires a good understanding of logic, and the willingness to learn the necessary mathematical background in model theory and comptational complexity theory.

Person specification

For information


Applicants will be required to evidence the following skills and qualifications.

  • This project requires mathematical engagement and ability substantially greater than for a typical Computer Science PhD. Give evidence for appropriate competence, as relevant to the project description.
  • You must be capable of performing at a very high level.
  • You must have a self-driven interest in uncovering and solving unknown problems and be able to work hard and creatively without constant supervision.


Applicants will be required to evidence the following skills and qualifications.

  • You will have good time management.
  • You will possess determination (which is often more important than qualifications) although you'll need a good amount of both.


Applicants will be required to address the following.

  • Comment on your transcript/predicted degree marks, outlining both strong and weak points.
  • Discuss your final year Undergraduate project work - and if appropriate your MSc project work.
  • How well does your previous study prepare you for undertaking Postgraduate Research?
  • Why do you believe you are suitable for doing Postgraduate Research?