Generalized completion problems with forbidden tournaments

DOI10.4230/LIPICS.MFCS.2024.28MaRDI QIDQ7241029zbMATH OpenFDO

Authors Zeno Bitter, Antoine Mottet

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2024.28

zbMATH Keywords

completion problemsconstraint satisfaction problemshomogeneous structurespolymorphismstournaments

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• \(2^{\aleph_{0}}\) pairwise nonisomorphic maximal-closed subgroups of \(\mathrm{Sym}(\mathbb N)\) via the classification of the reducts of the Henson digraphs
• A complexity dichotomy for poset constraint satisfaction
• A dichotomy for first-order reducts of unary structures
• A dichotomy theorem for nonuniform CSPs
• A proof of the CSP dichotomy conjecture
• An order out of nowhere: a new algorithm for infinite-domain CSPs
• Canonical functions: a proof via topological dynamics
• Collapsing the bounded width hierarchy for infinite-domain constraint satisfaction problems: when symmetries are enough
• Constraint satisfaction problems for reducts of homogeneous graphs
• Cores of Countably Categorical Structures
• CORES OVER RAMSEY STRUCTURES
• Decidability of definability
• Dualities for Constraint Satisfaction Problems
• Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
• Hrushovski's encoding and -categorical CSP monsters
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 3277470 (Why is no real title available?)
• Non-dichotomies in Constraint Satisfaction Complexity
• Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
• Smooth approximations and CSPs over finitely bounded homogeneous structures
• TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
• The Complexity of Equality Constraint Languages
• The complexity of temporal constraint satisfaction problems
• The partite construction and Ramsey set systems
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Topological Birkhoff
• When symmetries are not enough: a hierarchy of hard constraint satisfaction problems

Cited in

(1)

• Three fundamental questions in modern infinite-domain constraint satisfaction

This page was built for publication: Generalized completion problems with forbidden tournaments

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