Cookies

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.

Abstract

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
(351Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1016/j.tcs.2017.01.022
Publisher statement:© 2017 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
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

Export:
Export
Look up in GoogleScholar