Bounded-degree Forbidden-Pattern Problems are Constraint Satisfaction Problems
(2006)
Presentation / Conference Contribution
Dantchev, S., & Madelaine, F. (2006, December). Bounded-degree Forbidden-Pattern Problems are Constraint Satisfaction Problems. Presented at International Computer Science Symposium in Russia., St. Peterburg, Russia
Forbidden Pattern problem (FPP) is a proper generalisation of Constraint Satisfaction Problem (CSP). FPP is related to MMSNP, a logic introduced in relation with CSP by Feder and Vardi. We prove that Forbidden Pattern Problems are Constraint Satisfac... Read More about Bounded-degree Forbidden-Pattern Problems are Constraint Satisfaction Problems.