Equivalence constraint satisfaction problems

DOI10.4230/LIPICS.CSL.2012.122MaRDI QIDQ4649542zbMATH OpenFDO

Authors Manuel Bodirsky, Michał Wrona

Publication date 22 November 2012

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

zbMATH Keywords

computational complexityconstraint satisfaction problemsmodel theoryRamsey theorytemporal reasoninguniversal algebra

Mathematics Subject Classification ID

Temporal logic (03B44) Equational classes, universal algebra in model theory (03C05) Model theory of denumerable and separable structures (03C15) Ramsey theory (05D10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems
• The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
• Computer Science Logic
• Constraint Satisfaction with Countable Homogeneous Templates
• Constraint satisfaction problems for reducts of homogeneous graphs

Cited in

(17)

• Constants and finite unary relations in qualitative constraint reasoning
• scientific article; zbMATH DE number 1948177 (Why is no real title available?)
• The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems
• A dichotomy for first-order reducts of unary structures
• The language of stratified sets is confluent and strongly normalising
• Qualitative constraint satisfaction problems: an extended framework with landmarks
• scientific article; zbMATH DE number 1390058 (Why is no real title available?)
• Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
• The complexity of valued CSPs
• Tractable combinations of temporal CSPs
• The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems
• Canonical functions: a proof via topological dynamics
• Constraint satisfaction problems for reducts of homogeneous graphs
• Quantified Equality Constraints
• Equality detection for linear arithmetic constraints
• Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
• Smooth approximations and relational width collapses

This page was built for publication: Equivalence constraint satisfaction problems

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