The Complexity of Counting Quantifiers on Equality Languages

DOI10.1007/978-3-319-40189-8_34zbMath1476.68113OpenAlexW2466288635MaRDI QIDQ3188273

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

Publication date: 17 August 2016

Published in: Pursuit of the Universal (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/20827/1/20827.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70)

Related Items (1)

Quantified Constraints in Twenty Seventeen

Cites Work

• Unnamed Item
• Unnamed Item
• Quantifiers and cognition: logical and computational perspectives
• The complexity of equality constraint languages
• On the complexity of H-coloring
• On uniformity within \(NC^ 1\)
• The Complexity of Abduction for Equality Constraint Languages
• The reducts of equality up to primitive positive interdefinability
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Constraint Satisfaction with Counting Quantifiers
• Classifying the Complexity of Constraints Using Finite Algebras
• Quantified Equality Constraints
• The complexity of satisfiability problems

This page was built for publication: The Complexity of Counting Quantifiers on Equality Languages