Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T22:58:39.126Z Has data issue: false hasContentIssue false

Finite Conformal Hypergraph Covers and Gaifman Cliques in Finite Structures

Published online by Cambridge University Press:  15 January 2014

Ian Hodkinson
Affiliation:
Department of Computing, Imperial College London, London SW7 2AZ, UK E-mail: imh@doc.ic.ac.uk, URL: www.doc.ic.ac.uk/~imh
Martin Otto
Affiliation:
Department of Computer Science, University of Wales, Swansea, SA2 8PP, UK E-mail: m.otto@swan.ac.uk, URL: www-compsci.swan.ac.uk/~csmartin

Abstract

We provide a canonical construction of conformal covers for finite hypergraphs and present two immediate applications to the finite model theory of relational structures. In the setting of relational structures, conformal covers serve to construct guarded bisimilar companion structures that avoid all incidental Gaifman cliques—thus serving as a partial analogue in finite model theory for the usually infinite guarded unravellings. In hypergraph theoretic terms, we show that every finite hypergraph admits a bisimilar cover by a finite conformal hypergraph. In terms of relational structures, we show that every finite relational structure admits a guarded bisimilar cover by a finite structure whose Gaifman cliques are guarded. One of our applications answers an open question about a clique constrained strengthening of the extension property for partial automorphisms (EPPA) of Hrushovski, Herwig and Lascar. A second application provides an alternative proof of the finite model property (FMP) for the clique guarded fragment of first-order logic CGF, by reducing (finite) satisfiability in CGF to (finite) satisfiability in the guarded fragment, GF.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2003

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable