Madelaine, Florent R. - Universal Structures and the logic of Forbidden Patterns

lmcs:1237 - Logical Methods in Computer Science, June 2, 2009, Volume 5, Issue 2
Universal Structures and the logic of Forbidden Patterns

Authors: Madelaine, Florent R.

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

Source :
DOI : 10.2168/LMCS-5(2:13)2009
Volume: Volume 5, Issue 2
Published on: June 2, 2009
Submitted on: January 3, 2007
Keywords: Computer Science - Logic in Computer Science,Computer Science - Discrete Mathematics,F.4.1


Consultation statistics

This page has been seen 39 times.
This article's PDF has been downloaded 51 times.