The complexity of counting quantifiers on equality languages

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

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
• Public URL: https://durham-repository.worktribe.com/output/1387329