Search

Seese’s conjecture for finite graphs states that monadic second-order logic (MSO) is undecidable on all graph classes of unbounded clique-width. We show that to establish this it would suffice to show that grids of unbounded size can be inter- preted in two families of graph classes: minimal hereditary classes of unbounded clique-width; and antichains of unbounded clique-width under the induced sub- graph relation. We explore all the currently known classes of the former category and establish that grids of unbounded size can indeed be interpreted in them.

While structural width parameters (of the input) belong to the standard toolbox of graph algorithms, it is not the usual case in computational geometry. As a case study we propose a natural extension of the structural graph parameter of clique-width to geometric point configurations represented by their order type. We study basic properties of this clique-width notion, and relate it to the monadic second-order logic of point configurations. As an application, we provide several linear FPT time algorithms for geometric point problems which are NP-hard in general, in the special case that the input point set is of bounded clique-width and the clique-width expression is also given.

We present new parameterized preservation properties that provide for each natural number k, semantic characterizations of the ∃ k ∀ ⁎ and ∀ k ∃ ⁎ prefix classes of first order logic sentences, over the class of all structures and for arbitrary finite vocabularies. These properties, that we call preservation under substructures modulo k-cruxes and preservation under k-ary covered extensions respectively, correspond exactly to the classical properties of preservation under substructures and preservation under extensions, when k equals 0. As a consequence, we get a parameterized generalization of the Łoś–Tarski preservation theorem for sentences, in both its substructural and extensional forms. We call our characterizations collectively the generalized Łoś–Tarski theorem for sentences. We generalize this theorem to theories, by showing that theories that are preserved under k-ary covered extensions are characterized by theories of ∀ k ∃ ⁎ sentences, and theories that are preserved under substructures modulo k-cruxes, are equivalent, under a well-motivated model-theoretic hypothesis, to theories of ∃ k ∀ ⁎ sentences. In contrast to existing preservation properties in the literature that characterize the Σ 2 0 and Π 2 0 prefix classes of FO sentences, our preservation properties are combinatorial and finitary in nature, and stay non-trivial over finite structures as well.

We present a logic-based combinatorial property of classes of finite structures that allows an effective generalization of the Łoś-Tarski preservation theorem to hold over classes satisfying the property. The well-studied classes of words and trees, and structures of bounded tree-depth are shown to satisfy the property. We also show that starting with classes satisfying this property, the classes generated by applying composition operations like disjoint union, cartesian and tensor products, inherit the property. We finally show that all classes of structures that are well-quasi-ordered under the embedding relation satisfy a natural generalization of our property.

We investigate a model-theoretic property that generalizes the classical notion of preservation under substructures. We call this property preservation under substructures modulo bounded cores, and present a syntactic characterization via \(\Sigma_2^0\) sentences for properties of arbitrary structures definable by FO sentences. Towards a sharper characterization, we conjecture that the count of existential quantifiers in the \(\Sigma_2^0\) sentence equals the size of the smallest bounded core. We show that this conjecture holds for special fragments of FO and also over special classes of structures. We present a (not FO-definable) class of finite structures for which the conjecture fails, but for which the classical Łoś-Tarski preservation theorem holds. As a fallout of our studies, we obtain combinatorial proofs of the Łoś-Tarski theorem for some of the aforementioned cases.