Locally finite constraint satisfaction problems

DOI10.1109/LICS.2015.51MaRDI QIDQ4635828zbMATH OpenOpenAlexFDO

Authors Bartek Klin, Eryk Kopczyński, Joanna Ochremiak, Szymon Toruńczyk

Publication date 23 April 2018

Published in 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/lics.2015.51

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Equational classes, universal algebra in model theory (03C05) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A Characterisation of First-Order Constraint Satisfaction Problems
• Constraint Satisfaction Problems with Infinite Templates
• Computer Science Logic
• Complexity of infinite-domain constraint satisfaction

Cited in

(16)

• Limit Behavior of Locally Consistent Constraint Satisfaction Problems
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Turing machines with atoms, constraint satisfaction problems, and descriptive complexity
• A dichotomy for first-order reducts of unary structures
• The language of stratified sets is confluent and strongly normalising
• scientific article; zbMATH DE number 7136664 (Why is no real title available?)
• Linear equations with ordered data
• SMT solving for functional programming over infinite structures
• Canonical functions: a proof via topological dynamics
• scientific article; zbMATH DE number 7147443 (Why is no real title available?)
• Affine Systems of Equations and Counting Infinitary Logic
• A Characterisation of First-Order Constraint Satisfaction Problems
• Graph-Theoretic Concepts in Computer Science
• Solvability of orbit-finite systems of linear equations
• Orbit-finite linear programming
• Karp's NP-complete problems over first-order definable structures

This page was built for publication: Locally finite constraint satisfaction problems

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