The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
From MaRDI portal
Publication:4210136
Recommendations
- A Dichotomy Theorem for Typed Constraint Satisfaction Problems
- On the Computational Complexity of Monotone Constraint Satisfaction Problems
- scientific article; zbMATH DE number 1670830
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- A proof of the CSP dichotomy conjecture
Cited in
(only showing first 100 items - show all)- Polyadic sets and homomorphism counting
- Correspondence homomorphisms to reflexive graphs
- \(n\)-permutability and linear Datalog implies symmetric Datalog
- First-Order Model Checking Problems Parameterized by the Model
- ASNP: a tame fragment of existential second-order logic
- A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
- A dichotomy for first-order reducts of unary structures
- Galois connections for patterns: an algebra of labelled graphs
- High girth hypergraphs with unavoidable monochromatic or rainbow edges
- Semilattice polymorphisms and chordal graphs
- Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
- Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
- From \(A\) to \(B\) to \(Z\)
- Permutation groups with small orbit growth
- Quantified constraint satisfaction problem on semicomplete digraphs
- Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
- Proof Complexity Meets Algebra
- NP for Combinatorialists
- Tractable combinations of theories via sampling
- Constraint satisfaction problems for reducts of homogeneous graphs
- A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
- The number of clones determined by disjunctions of unary relations
- Parameterized counting of partially injective homomorphisms
- Decidability of absorption in relational structures of bounded width.
- Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
- A tetrachotomy of ontology-mediated queries with a covering axiom
- The quantum monad on relational structures
- Dichotomy for tree-structured trigraph list homomorphism problems
- On rainbow-free colourings of uniform hypergraphs
- Uniform and nonuniform recognizability.
- The complexity of quantified constraints using the algebraic formulation
- The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
- Dismantlability, connectedness, and mixing in relational structures
- A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
- Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
- Computational complexity of various Mal'cev conditions
- The Complexity of Counting Quantifiers on Equality Languages
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- Join colourings of chordal graphs
- Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
- On the CSP Dichotomy Conjecture
- Decomposing Quantified Conjunctive (or Disjunctive) Formulas
- Why is it hard to obtain a dichotomy for consistent query answering?
- Counting List Matrix Partitions of Graphs
- Homomorphism reconfiguration via homotopy
- Surjective \(H\)-colouring: new hardness results
- Binarisation for valued constraint satisfaction problems
- Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
- Quasi-transitive digraphs and their extensions
- On the Complexity of Holant Problems
- Emptiness problems for distributed automata
- Binary constraint satisfaction problems defined by excluded topological minors
- A complete dichotomy rises from the capture of vanishing signatures
- Computational complexity of auditing finite attributes in statistical databases
- Tropically convex constraint satisfaction
- CSP dichotomy for special polyads
- Complexity of correspondence \(H\)-colourings
- The power of Sherali-Adams relaxations for general-valued CSPs
- A Galois connection for valued constraint languages of infinite size
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- Absorption in universal algebra and CSP
- Algebra and the complexity of digraph CSPs: a survey
- A surprising permanence of old motivations (a not-so-rigid story)
- Peek arc consistency
- Reconfiguration in bounded bandwidth and tree-depth
- On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
- On the restricted homomorphism problem
- On tree-preserving constraints
- Partially ordered connectives and monadic monotone strict NP
- Robustly solvable constraint satisfaction problems
- Extension problems with degree bounds
- scientific article; zbMATH DE number 7561584 (Why is no real title available?)
- A Generalized Version of the Baker–Pixley Theorem
- Axiomatisability and hardness for universal Horn classes of hypergraphs
- On algebras with many symmetric operations
- The \(C_{k}\)-extended graft construction
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Circuit satisfiability and constraint satisfaction around Skolem arithmetic
- A finite-model-theoretic view on propositional proof complexity
- There are no pure relational width 2 constraint satisfaction problems
- Circuit satisfiability and constraint satisfaction around Skolem arithmetic
- The wonderland of reflections
- Logical compactness and constraint satisfaction problems
- A structured view on weighted counting with relations to counting, quantum computation and applications
- A discrete homotopy theory for binary reflexive structures
- A new line of attack on the dichotomy conjecture
- Computational complexity of covering three-vertex multigraphs
- The power of propagation: when GAC is enough
- The structure of bi-arc trees
- Complexity of clausal constraints over chains
- Relativised homomorphism preservation at the finite level
- Determining the consistency of partial tree descriptions
- Towards a characterization of constant-factor approximable finite-valued CSPs
- The Helly property and satisfiability of Boolean formulas defined on set families
- Absolute retracts and varieties generated by chordal graphs
- Dichotomy for finite tournaments of mixed-type
- Tractability of quantified temporal constraints to the max
- The complexity of valued CSPs
This page was built for publication: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210136)
