Skip to main content

Research Repository

Advanced Search

Outputs (4)

Constraint satisfaction, logic and forbidden patterns (2007)
Journal Article
Madelaine, F., & Stewart, I. (2007). Constraint satisfaction, logic and forbidden patterns. SIAM Journal on Computing, 37(1), 132-163. https://doi.org/10.1137/050634840

In the early nineties, Feder and Vardi attempted to find a large sub-class of NP which exhibits a dichotomy; that is, where every problem in the sub-class is either solvable in polynomial-time or NP-complete. Their studies resulted in a candidate cla... Read More about Constraint satisfaction, logic and forbidden patterns.

Bounded-degree Forbidden-Pattern Problems are Constraint Satisfaction Problems (2006)
Conference Proceeding
Dantchev, S., & Madelaine, F. (2006). Bounded-degree Forbidden-Pattern Problems are Constraint Satisfaction Problems. In D. Grigoriev, J. Harrison, & E. A. Hirsch (Eds.), . https://doi.org/10.1007/11753728_18

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.

Dichotomies for classes of homomorphism problems involving unary functions (2004)
Journal Article
Feder, T., Madelaine, F., & Stewart, I. (2004). Dichotomies for classes of homomorphism problems involving unary functions. Theoretical Computer Science, 314(1-2), 1-43. https://doi.org/10.1016/j.tcs.2003.12.015

We study non-uniform constraint satisfaction problems where the underlying signature contains constant and function symbols as well as relation symbols. Amongst our results are the following. We establish a dichotomy result for the class of non-unifo... Read More about Dichotomies for classes of homomorphism problems involving unary functions.

Some problems not definable using structure homomorphisms (2003)
Journal Article
Madelaine, F., & Stewart, I. (2003). Some problems not definable using structure homomorphisms. Ars combinatoria, 67, 153-159

We exhibit some problems definable in Feder and Vardi's logic MMSNP that are not in the class CSP of constraint satisfaction problems. Whilst some of these problems have previously been shown to be in MMSNP (that is, definable in MMSNP) but not in CS... Read More about Some problems not definable using structure homomorphisms.