A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
From MaRDI portal
Publication:4957913
DOI10.1137/19M128466XWikidataQ123135727 ScholiaQ123135727MaRDI QIDQ4957913
Florent R. Madelaine, Antoine Mottet, Manuel Bodirsky
Publication date: 10 September 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/19m128466x
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(H\)-coloring dichotomy revisited
- Universal graphs with forbidden subgraphs and algebraic closure
- The wonderland of reflections
- Datalog and constraint satisfaction with infinite templates
- All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)
- Constraints, MMSNP and expander relational structures
- Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups
- Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
- On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction
- A Model-Theoretic View on Qualitative Constraint Reasoning
- Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics (Invited Talk).
- Constraint Satisfaction with Countable Homogeneous Templates
- Universal Structures and the logic of Forbidden Patterns
- 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
- Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
- PROJECTIVE CLONE HOMOMORPHISMS
- 𝜔-categorical structures avoiding height 1 identities
- Universal Structures with Forbidden Homomorphisms
- Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
- Monotone monadic SNP and constraint satisfaction
- Cores of Countably Categorical Structures
- Classifying the Complexity of Constraints Using Finite Algebras
- A Characterisation of First-Order Constraint Satisfaction Problems
- Constraint Satisfaction, Logic and Forbidden Patterns
- On the Relationship between Consistent Query Answering and Constraint Satisfaction Problems
