The Complexity of Counting Quantifiers on Equality Languages

DOI10.1007/978-3-319-40189-8_34MaRDI QIDQ3188273zbMATH OpenOpenAlexFDO

Authors Barnaby Martin, András Pongrácz, 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

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

Recommendations

• The complexity of counting quantifiers on equality languages
• The complexity of equality constraint languages
• The Complexity of Equality Constraint Languages
• The complexity of counting problems in equational matching
• The complexity of counting problems in equational matching
• scientific article; zbMATH DE number 3845566
• The quantifier complexity of NF
• The complexity of countable categoricity in finite languages
• Expressive Power and Complexity of a Logic with Quantifiers that Count Proportions of Sets
• Complexity classes defined by counting quantifiers

Cites work

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

Cited in

(6)

• Easy solutions for a hard problem? The computational complexity of reciprocals with quantificational antecedents
• The Complexity of Abduction for Equality Constraint Languages
• The Complexity of Equality Constraint Languages
• Quantified Constraints in Twenty Seventeen
• The complexity of counting quantifiers on equality languages
• The complexity of equality constraint 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 Q3188273)