Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Preservation Under Extensions on Well-Behaved Finite Structures
verfasst von : Albert Atserias, Anuj Dawar, Martin Grohe
Erschienen in: Automata, Languages and Programming
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
A class of relational structures is said to have the extension preservation property if every first-order sentence that is preserved under extensions on the class is equivalent to an existential sentence. The class of all finite structures does not have the extension preservation property. We study the property on classes of finite structures that are better behaved. We show that the property holds of classes of acyclic structures, structures of bounded degree and more generally structures that are
wide
in a sense we make precise. We also show that the preservation property holds for the class of structures of treewidth at most
k
, for any
k
. In contrast, we show that the property fails for the class of planar graphs.