The complexity of counting quantifiers on equality languages

Martin, Barnaby; Pongrácz, András; Wrona, Michał

doi:10.1016/j.tcs.2017.01.022

The complexity of counting quantifiers on equality languages

Martin, Barnaby; Pongrácz, András; Wrona, Michał

Authors

Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor

András Pongrácz

Michał Wrona

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.

Citation

Martin, B., Pongrácz, A., & Wrona, M. (2017). The complexity of counting quantifiers on equality languages. Theoretical Computer Science, 670, 56-67. https://doi.org/10.1016/j.tcs.2017.01.022

Journal Article Type	Article
Acceptance Date	Jan 24, 2017
Online Publication Date	Jan 31, 2017
Publication Date	Mar 29, 2017
Deposit Date	Feb 1, 2017
Publicly Available Date	Jan 31, 2018
Journal	Theoretical Computer Science
Print ISSN	0304-3975
Publisher	Elsevier
Peer Reviewed	Peer Reviewed
Volume	670
Pages	56-67
DOI	https://doi.org/10.1016/j.tcs.2017.01.022

Files

Accepted Journal Article (359 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/

Copyright 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/