Universal Structures and the Logic of Forbidden Patterns

DOI10.1007/11874683_31MaRDI QIDQ3613358zbMATH OpenOpenAlexFDO

Authors Florent R. Madelaine

Publication date 12 March 2009

Published in Computer Science Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0904.2521

zbMATH Keywords

constraint satisfactiondualityfinite model theorygraph homomorphismmonadic second-order logic

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

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

Recommendations

• Universal Structures and the logic of Forbidden Patterns
• Bounded-Degree Forbidden Patterns Problems Are Constraint Satisfaction Problems
• Constraint Satisfaction, Logic and Forbidden Patterns
• The tractability of CSP classes defined by forbidden patterns
• scientific article; zbMATH DE number 2191987

Cited in

(3)

• ASNP: a tame fragment of existential second-order logic
• Bounded-Degree Forbidden Patterns Problems Are Constraint Satisfaction Problems
• Universal Structures and the logic of Forbidden Patterns

This page was built for publication: Universal Structures and the Logic of Forbidden Patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3613358)