Preservation under Extensions on Well-Behaved Finite Structures
Albert Atserias, Anuj Dawar, Martin Grohe · SIAM Journal on Computing · 2008
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 for classes of acyclic structures, structures of bounded degree, and more generally structures that are wide in a sense that we will 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.