On guarded extensions of MMSNP

DOI10.46298/LMCS-21(4:15)2025MaRDI QIDQ6858439zbMATH OpenFDO

Authors Alexey Barsukov, Florent R. Madelaine

Publication date 13 February 2026

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/LMCS-21(4:15)2025

zbMATH Keywords

computational complexityconstraint satisfaction problemdescriptive complexitydichotomyMMSNP

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites work

• A dichotomy theorem for nonuniform CSPs
• A proof of the CSP dichotomy conjecture
• ASNP: a tame fragment of existential second-order logic
• Complexity of infinite-domain constraint satisfaction
• Generalisations of matrix partitions: complexity and obstructions
• Graph partitions with prescribed patterns
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 545277 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• On the complexity of H-coloring
• On the Structure of Polynomial Time Reducibility
• Ontology-based data access: a study through disjunctive Datalog, CSP, and MMSNP
• PROJECTIVE CLONE HOMOMORPHISMS
• Relations Among Complexity Measures
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The effect of two cycles on the complexity of colourings by directed graphs
• Universal Structures and the logic of Forbidden Patterns

This page was built for publication: On guarded extensions of MMSNP

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