Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
On the Containment of Forbidden Patterns Problems
verfasst von : Florent Madelaine
Erschienen in: Principles and Practice of Constraint Programming – CP 2010
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Forbidden patterns problems are a generalisation of (finite) constraint satisfaction problems which are definable in Feder and Vardi’s logic
mmsnp
[1]. In fact, they are examples of infinite constraint satisfaction problems with nice model theoretic properties introduced by Bodirsky [2]. In previous work [3], we introduced a normal form for these forbidden patterns problems which allowed us to provide an effective characterisation of when a problem is a finite or infinite constraint satisfaction problem. One of the central concepts of this normal form is that of a
recolouring
. In the presence of a recolouring from a forbidden patterns problem Ω
1
to another forbidden patterns problem Ω
2
, containment of Ω
1
in Ω
2
follows. The converse does not hold in general and it remained open whether it did in the case of problems being given in our normal form. In this paper, we prove that this is indeed the case. We also show that the recolouring problem is
$\Pi^p_2$
-hard and in
$\Sigma^p_3$
.