The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
From MaRDI portal
Publication:4210136
DOI10.1137/S0097539794266766zbMATH Open0914.68075OpenAlexW2150339067WikidataQ56389117 ScholiaQ56389117MaRDI QIDQ4210136FDOQ4210136
Authors: Moshe Y. Vardi, Tomás Feder 
Publication date: 21 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539794266766
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
Discrete mathematics in relation to computer science (68R99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (only showing first 100 items - show all)
- In praise of homomorphisms
- Tractability of quantified temporal constraints to the max
- OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT
- A discrete homotopy theory for binary reflexive structures
- The Helly property and satisfiability of Boolean formulas defined on set families
- Absolute retracts and varieties generated by chordal graphs
- There are no pure relational width 2 constraint satisfaction problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Dichotomy for finite tournaments of mixed-type
- A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP
- The structure of bi-arc trees
- Algebraic properties of valued constraint satisfaction problem
- Binary constraint satisfaction problems defined by excluded topological minors
- Some complete and intermediate polynomials in algebraic complexity theory
- Tropically convex constraint satisfaction
- The power of Sherali-Adams relaxations for general-valued CSPs
- The power of propagation: when GAC is enough
- A finite-model-theoretic view on propositional proof complexity
- Circuit satisfiability and constraint satisfaction around Skolem arithmetic
- Circuit satisfiability and constraint satisfaction around Skolem arithmetic
- Reconfiguration in bounded bandwidth and tree-depth
- The \(C_{k}\)-extended graft construction
- Axiomatisability and hardness for universal Horn classes of hypergraphs
- Complexity of clausal constraints over chains
- Relativised homomorphism preservation at the finite level
- Building blocks for the variety of absolute retracts
- Determining the consistency of partial tree descriptions
- What makes propositional abduction tractable
- Partially ordered connectives and monadic monotone strict NP
- Extension problems with degree bounds
- A new line of attack on the dichotomy conjecture
- Computational complexity of covering three-vertex multigraphs
- A complete dichotomy rises from the capture of vanishing signatures
- A Galois connection for valued constraint languages of infinite size
- Towards a characterization of constant-factor approximable finite-valued CSPs
- The complexity of valued CSPs
- The recognition of bound quivers using edge-coloured homomorphisms
- A surprising permanence of old motivations (a not-so-rigid story)
- Peek arc consistency
- On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
- Logical compactness and constraint satisfaction problems
- Learnability of solutions to conjunctive queries
- Computational complexity of auditing finite attributes in statistical databases
- Complexity of correspondence \(H\)-colourings
- Model checking existential logic on partially ordered sets
- Robustly solvable constraint satisfaction problems
- On algebras with many symmetric operations
- Title not available (Why is that?)
- On the restricted homomorphism problem
- A Generalized Version of the Baker–Pixley Theorem
- List-homomorphism problems on graphs and arc consistency
- Residual properties of simple graphs
- Distance constraint satisfaction problems
- A dichotomy for real weighted Holant problems
- A Logical Approach to Constraint Satisfaction
- Graph partitions with prescribed patterns
- The complexity of surjective homomorphism problems-a survey
- Title not available (Why is that?)
- Recent Results on the Algebraic Approach to the CSP
- Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
- Tractability in constraint satisfaction problems: a survey
- Enumerating homomorphisms
- Colouring, constraint satisfaction, and complexity
- TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
- Dualities for Constraint Satisfaction Problems
- Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
- Uniform Constraint Satisfaction Problems and Database Theory
- The complexity of weighted Boolean \#CSP with mixed signs
- Tractable structures for constraint satisfaction with truth tables
- Datalog rewritability of disjunctive Datalog programs and non-Horn ontologies
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Hybrid tractability of valued constraint problems
- The complexity of counting homomorphisms seen from the other side
- Backdoors into heterogeneous classes of SAT and CSP
- View-based query processing: on the relationship between rewriting, answering and losslessness
- Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
- Conservative constraint satisfaction re-revisited
- Maximal infinite-valued constraint languages
- Relatively quantified constraint satisfaction
- An approximation trichotomy for Boolean \#CSP
- Computing hypergraph width measures exactly
- On the complexity of the model checking problem
- Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
- A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
- Constraint satisfaction problems over the integers with successor
- Nonnegative weighted \#CSP: an effective complexity dichotomy
- Conjunctive-query containment and constraint satisfaction
- From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems
- The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
- A new tractable class of constraint satisfaction problems
- Majority constraints have bounded pathwidth duality
- Locally constrained graph homomorphisms -- structure, complexity, and applications
- The complexity of general-valued CSPs
- Constraint satisfaction with succinctly specified relations
- Constraint satisfaction problems over numeric domains
- Maltsev digraphs have a majority polymorphism
- Homomorphisms of sparse signed graphs
- \(H\)-coloring dichotomy revisited
- The complexity of constraint satisfaction games and QCSP
Uses Software
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)
