Logical compactness and constraint satisfaction problems

DOI10.23638/LMCS-13(1:1)2017zbMath1448.03020arXiv1609.05221MaRDI QIDQ2980963

David L. Wehlau, Danny Rorabaugh, Claude Tardif

Publication date: 8 May 2017

Full work available at URL: https://arxiv.org/abs/1609.05221

zbMATH Keywords

constraint satisfaction problemsrelational structurescompactness theorem

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Other combinatorial set theory (03E05) Models with special properties (saturated, rigid, etc.) (03C50) Other set-theoretic hypotheses and axioms (03E65) Relational systems, laws of composition (08A02) Basic properties of first-order languages and structures (03C07) Descriptive complexity and finite models (68Q19)

Related Items (2)

CLAP: A New Algorithm for Promise CSPs ⋮ The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems

Cites Work

• Unnamed Item
• Coloring infinite graphs and the Boolean prime ideal theorem
• Applications of product colouring
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Axiom of choice for finite sets
• The axiom of choice

This page was built for publication: Logical compactness and constraint satisfaction problems