Attend the Virtual Global Study Fair | Register Now Attend the Virtual Global Study Fair | Register Now

Computational Logic: Super-Counting Quantifiers

   Department of Computer Science

This project is no longer listed on and may not be available.

Click here to search for PhD studentship opportunities
  Dr I Pratt-Hartmann  Applications accepted all year round  Competition Funded PhD Project (Students Worldwide)

About the Project

Many problems in computational logic reduce to the so-called 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 large such fragment is the two-variable fragment with counting quantifiers, usually denoted C2. In this fragment, only two logical variables, x and y may appear; however, we can use counting quantifiers of the form "There exist M x such that ....", where M is a natural number. The complexity-theoretic properties of this fragment have been understood for some years.

Very recently, it has been shown that counting quantifiers can be generalized without losing decidability. Thus, for example, C2 can be extended with counting modulo k for some fixed k, thus giving us expressions like "There exist an even number of x such that ....". It seems clear that this extension is a special case of a more general kind of quantifier in which certain "local patterns" of relations are specified using various computational models. The aim of this project is to establish the extent to which counting quantifiers can be thus generalized. It is expected that this work will have an impact developements in description logics and related applications. The research may 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 graph theory, model theory and comptational complexity theory.

Funding Notes

Applications are invited from self-funded students. This project has a Band 1 fee.
Equality, diversity and inclusion is fundamental to the success of The University of Manchester, and is at the heart of all of our activities. The full Equality, diversity and inclusion statement can be found on the website


Ian Pratt-Hartmann "Complexity of the Two-Variable Fragment with Counting Quantifiers' , Journal of Logic, Language and Information, 14(3), 2005, pp. 369--395.

How good is research at The University of Manchester in Computer Science and Informatics?

Research output data provided by the Research Excellence Framework (REF)

Click here to see the results for all UK universities
Search Suggestions
Search suggestions

Based on your current searches we recommend the following search filters.

PhD saved successfully
View saved PhDs