The complexity of counting quantifiers on equality languages

DOI10.1016/J.TCS.2017.01.022zbMATH Open1359.68138OpenAlexW2583763929MaRDI QIDQ515549FDOQ515549

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

Publication date: 16 March 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

Recommendations

• The Complexity of Counting Quantifiers on Equality Languages
• The complexity of equality constraint languages
• Quantified Equality Constraints
• The Complexity of Equality Constraint Languages
• Constraint satisfaction with counting quantifiers

zbMATH Keywords

computational complexityconstraint satisfactioncounting quantifiersequality languagequantified constraints

Mathematics Subject Classification ID

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

Cites Work

• Quantifiers and cognition: logical and computational perspectives
• On the complexity of H-coloring
• On uniformity within \(NC^ 1\)
• On the scope of the universal-algebraic approach to constraint satisfaction
• The reducts of equality up to primitive positive interdefinability
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Undirected connectivity in log-space
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Classifying the Complexity of Constraints Using Finite Algebras
• The complexity of satisfiability problems
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The complexity of equality constraint languages
• The polynomial-time hierarchy
• Title not available (Why is that?)
• The complexity of constraint satisfaction games and QCSP
• Title not available (Why is that?)
• The Complexity of Abduction for Equality Constraint Languages
• Title not available (Why is that?)
• Positive First-Order Logic Is NP-Complete
• Constraint satisfaction with counting quantifiers
• Quantified Equality Constraints

Cited In (4)

• The complexity of equality constraint languages
• The Complexity of Equality Constraint Languages
• The Complexity of Abduction for Equality Constraint Languages
• The Complexity of Counting Quantifiers on Equality Languages

This page was built for publication: The complexity of counting quantifiers on equality languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q515549)