Quantified constraint satisfaction on monoids

DOI10.4230/LIPICS.CSL.2016.15MaRDI QIDQ5278401zbMATH OpenFDO

Authors Hubie Chen, Peter Mayr

Publication date 19 July 2017

Full work available at URL https://doi.org/10.4230/LIPICS.CSL.2016.15

zbMATH Keywords

computational complexityquantified constraint satisfactionuniversal algebra

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Applications of universal algebra in computer science (08A70) Semigroups in automata theory, linguistics, etc. (20M35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)

Recommendations

• Meditations on quantified constraint satisfaction
• Quantified Equality Constraints
• STACS 2005
• Quantified Constraint Satisfaction and the Polynomially Generated Powers Property
• Quantified constraint satisfaction and the polynomially generated powers property

Cited in

(8)

• The number of clones determined by disjunctions of unary relations
• Meditations on quantified constraint satisfaction
• scientific article; zbMATH DE number 1223636 (Why is no real title available?)
• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• The Monotone Satisfiability Problem with Bounded Variable Appearances
• Quantified Constraints in Twenty Seventeen
• The complexity of quantified constraints using the algebraic formulation
• The Complexity of Quantified Constraints: Collapsibility, Switchability, and the Algebraic Formulation

This page was built for publication: Quantified constraint satisfaction on monoids

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