Constraint Satisfaction, Logic and Forbidden Patterns

DOI10.1137/050634840MaRDI QIDQ5454246zbMATH OpenOpenAlexFDO

Authors Florent R. Madelaine, Iain Stewart

Publication date 28 March 2008

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://dro.dur.ac.uk/3987/1/3987.pdf

zbMATH Keywords

constraint satisfactionexistential monadic second-order logicfinite model theory

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• The logic of constraint satisfaction
• Methods and Applications of Artificial Intelligence
• A Logical Approach to Constraint Satisfaction
• Constraint Satisfaction
• Logical compactness and constraint satisfaction problems
• Constraint satisfaction from a deductive viewpoint
• Constraint satisfaction using constraint logic programming
• scientific article; zbMATH DE number 1670830
• Bounded-Degree Forbidden Patterns Problems Are Constraint Satisfaction Problems
• scientific article; zbMATH DE number 1059315

Cited in

(16)

• Partially ordered connectives and monadic monotone strict NP
• Binary constraint satisfaction problems defined by excluded topological minors
• Forbidden lifts (NP and CSP for combinatorialists)
• Many Facets of Dualities
• On the CSP Dichotomy Conjecture
• Bounded-Degree Forbidden Patterns Problems Are Constraint Satisfaction Problems
• Universal Structures and the Logic of Forbidden Patterns
• Universal Structures and the logic of Forbidden Patterns
• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• A universal-algebraic proof of the complexity dichotomy for monotone monadic SNP
• Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
• Hierarchies in Fragments of Monadic Strict NP
• scientific article; zbMATH DE number 2191987 (Why is no real title available?)
• On guarded extensions of MMSNP
• Complexity classification transfer for CSPs via algebraic products
• Smooth approximations and relational width collapses

This page was built for publication: Constraint Satisfaction, Logic and Forbidden Patterns

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