Computer Science – Logic in Computer Science
Scientific paper
2009-04-16
LMCS 5 (2:13) 2009
Computer Science
Logic in Computer Science
25 pages, 3 figures, extended version of conference papers at CSR'06 and CSL'06
Scientific paper
10.2168/LMCS-5(2:13)2009
Forbidden Patterns Problems (FPPs) are a proper generalisation of Constraint Satisfaction Problems (CSPs). However, we show that when the input is connected and belongs to a class which has low tree-depth decomposition (e.g. structure of bounded degree, proper minor closed class and more generally class of bounded expansion) any FPP becomes a CSP. This result can also be rephrased in terms of expressiveness of the logic MMSNP, introduced by Feder and Vardi in relation with CSPs. Our proof generalises that of a recent paper by Nesetril and Ossona de Mendez. Note that our result holds in the general setting of problems over arbitrary relational structures (not just for graphs).
No associations
LandOfFree
Universal Structures and the logic of Forbidden Patterns does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Universal Structures and the logic of Forbidden Patterns, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Universal Structures and the logic of Forbidden Patterns will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-465238