We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

The complexity of counting quantifiers on equality languages.

Martin, Barnaby and Pongrácz, András and Wrona, Michał (2017) 'The complexity of counting quantifiers on equality languages.', Theoretical computer science., 670 . pp. 56-67.


An equality language is a relational structure with infinite domain whose relations are first-order definable in equality. We classify the extensions of the quantified constraint satisfaction problem over equality languages in which the native existential and universal quantifiers are augmented by some subset of counting quantifiers. In doing this, we find ourselves in various worlds in which dichotomies or trichotomies subsist.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
Publisher Web site:
Publisher statement:© 2017 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:24 January 2017
Date deposited:01 February 2017
Date of first online publication:31 January 2017
Date first made open access:31 January 2018

Save or Share this output

Look up in GoogleScholar