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

lmcs:1237 - Logical Methods in Computer Science, June 2, 2009, Volume 5, Issue 2 - https://doi.org/10.2168/LMCS-5(2:13)2009
Universal Structures and the logic of Forbidden Patterns

Authors: Florent R. Madelaine

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

Volume: Volume 5, Issue 2
Published on: June 2, 2009
Accepted on: June 25, 2015
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 325 times.
This article's PDF has been downloaded 3066 times.