Universal Structures and the logic of Forbidden Patterns

Details Universal Structures and the logic of Forbidden Patterns Universal Structures and the logic of Forbidden Patterns

2009-04-16

arxiv.org/abs/0904.2521v2

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).

Affiliated with

Also associated with

No associations

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-465238