Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures

DOI10.1142/S0219061319500107zbMath1477.03118arXiv1612.07551OpenAlexW2963710712MaRDI QIDQ4973030

Miroslav Olšák, Trung van Pham, Michael Pinsker, Libor Barto, Michael Kompatscher

Publication date: 29 November 2019

Published in: Journal of Mathematical Logic (Search for Journal in Brave)

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

zbMATH Keywords

constraint satisfaction problemMal'cev conditionomega-categoricitydichotomy conjectureorbit growthpolymorphism clonemodel-complete core

Mathematics Subject Classification ID

Equational logic, Mal'tsev conditions (08B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Operations and polynomials in algebraic structures, primal algebras (08A40) Equational classes, universal algebra in model theory (03C05) Interpolation, preservation, definability (03C40) Infinite automorphism groups (20B27) Categoricity and completeness of theories (03C35)

Related Items (11)

Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting) ⋮ When Symmetries Are Not Enough: A Hierarchy of Hard Constraint Satisfaction Problems ⋮ 𝜔-categorical structures avoiding height 1 identities ⋮ Solving equation systems in ω-categorical algebras ⋮ Pseudo‐loop conditions ⋮ An algebraic view on p-admissible concrete domains for lightweight description logics ⋮ Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems) ⋮ PROJECTIVE CLONE HOMOMORPHISMS ⋮ CORES OVER RAMSEY STRUCTURES ⋮ Using model theory to find decidable and tractable description logics with concrete domains ⋮ ASNP: a tame fragment of existential second-order logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fraïssé sequences: category-theoretic approach to universal homogeneous structures
• \({\aleph_{0}}\)-categorical structures: endomorphisms and interpretations
• The complexity of equality constraint languages
• Theory of relations. Transl. from the French by P. Clote
• A counterexample to the reconstruction of \(\omega\)-categorical structures from their endomorphism monoid
• A uniform Birkhoff theorem
• Uniform Birkhoff
• The wonderland of reflections
• A survey of homogeneous structures
• Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups
• Towards a Ryll-Nardzewski-type theorem for weakly oligomorphic structures
• Schaefer's Theorem for Graphs
• On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction
• Reconstructing the topology of clones
• Reducts of Ramsey structures
• Non-dichotomies in Constraint Satisfaction Complexity
• The complexity of temporal constraint satisfaction problems
• Reducts of the random graph
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
• A complexity dichotomy for poset constraint satisfaction
• PROJECTIVE CLONE HOMOMORPHISMS
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• Cores of Countably Categorical Structures
• Topological Birkhoff
• Sur l'extension aux relations de quelques propriétés des ordres

This page was built for publication: Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures