Library

An Application of Farkas' Lemma to Finite-Valued Constraint Satisfaction Problems over Infinite Domains

We show a universal algebraic local characterisation of the expressive power of finite-valued languages with domains of arbitrary cardinality and containing arbitrary many cost functions.

MathematicsComputer Science
View graphSource

Paper

Similar papers

Submodular Functions and Valued Constraint Satisfaction Problems over Infinite DomainsM. Bodirsky, M. Mamino, C. Viola2018 · Annual Conference for Computer Science Logic · 3 citations In Library
Constraint satisfaction tractability from semi-lattice operations on infinite setsM. Bodirsky, D. Macpherson, Johan Thapper2011 · TOCL · 9 citations In Library
Complexity of Infinite-Domain Constraint SatisfactionM. Bodirsky2021 · 101 citations In Library
Complexity Classification in Infinite-Domain Constraint SatisfactionM. Bodirsky2012 · arXiv.org · 100 citations In Library
The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction ProblemsL. Barto, M. Pinsker2016 · Logic in Computer Science · 89 citations In Library
Finite model theory for pseudovarieties and universal algebra: preservation, definability and complexityLucy Ham, Marcel Jackson2022 · arXiv (Cornell University) In Library
Applications of Partial Polymorphisms in (Fine-Grained) Complexity of Constraint Satisfaction ProblemsBiman Roy2020 · Linköping studies in science and technology, Dissertations · 1 citation In Library
Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hardLeonid Dorochko, Michal Wrona2026 · arXiv.org · 0 citations In Library
On the Descriptive Complexity of Temporal Constraint Satisfaction ProblemsM. Bodirsky, Jakub Rydval2020 · Journal of the ACM · 16 citations In Library
Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite SheepM. Pinsker2022 · IEEE International Symposium on Multiple-Valued Logic · 17 citations In Library
© 2026 NYSGPT2525 LLC