The complexity of counting quantifiers on equality languages
type: Item
instance of: scholarly article
title: The complexity of counting quantifiers on equality languages
zbMATH Open document ID: 1359.68138
author: Barnaby Martin
author: András Pongrácz
author: Michał Wrona
published in: Theoretical Computer Science
publication date: 2017-03-16T00:00:00Z
full work available at URL: 20827.pdf
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03B70
zbMATH DE Number: 6695551
zbMATH Keywords: quantified constraints
zbMATH Keywords: counting quantifiers
zbMATH Keywords: constraint satisfaction
zbMATH Keywords: equality language
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
OpenAlex ID: W2583763929
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: Classifying the Complexity of Constraints Using Finite Algebras
cites work: The complexity of satisfiability problems
cites work: A dichotomy theorem for constraint satisfaction problems on a 3-element set
cites work: On the complexity of H-coloring
cites work: The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
cites work: The complexity of equality constraint languages
cites work: Quantified Equality Constraints
cites work: Constraint Satisfaction with Counting Quantifiers
cites work: Q4255575
cites work: Q4332930
cites work: Q3735686
cites work: Quantifiers and cognition: logical and computational perspectives
cites work: On uniformity within \(NC^ 1\)
cites work: The reducts of equality up to primitive positive interdefinability
cites work: The Complexity of Abduction for Equality Constraint Languages
cites work: On the scope of the universal-algebraic approach to constraint satisfaction
cites work: The complexity of constraint satisfaction games and QCSP
cites work: The polynomial-time hierarchy
cites work: Positive First-Order Logic Is NP-Complete
cites work: Undirected connectivity in log-space
DOI: 10.1016/J.TCS.2017.01.022
description: scientific article; zbMATH DE number 6695551