Publications Home » Finite conformal hypergraph cover...
Finite conformal hypergraph covers and Gaifman cliques in finite structures
Ian Hodkinson, Martin Otto
- Journal Article
- Bulletin of Symbolic Logic
- Volume 9
- Issue 3
- pp.387–405
- 2003
- ISSN 1079-8986
- Abstract
Every finite hypergraph is shown to admit a cover by a finite conformal hypergraph. The notion of a hypergraph cover is based on homomorphisms that induce a bisimulation like back-and-forth system of local bijections between hyperedges. It is here introduced to capture the essential features of guarded bisimulations in the hypergraph setting. The classical hypergraph notion of conformality, defined by the requirement that all induced cliques be contained within hyperedges, thus corresponds to the collapse of clique guardedness to plain guardedness. As far as conformality is concerned, our construction can serve as a substitute in finite model theory for the straightforward but generally infinite unravelling of hypergraphs or relational structures.
Two immediate applications to the finite model theory of relational structures are presented:
1. The construction is used to solve an open problem about a clique constrained strengthening of the extension property for partial automorphisms (EPPA) of Hrushovski, Herwig and Lascar. EPPA is thus established for the class of finite conformal structures, of any relational type. This also gives a simplified route to the known EPPA for the class of finite Kn-free graphs.
2. Finite conformal covers can be used in a straightforward reduction from the clique guarded fragment CGF (and the loosely guarded fragment LGF) to the guarded fragment GF, which is adequate for finite satisfiability. This gives a new simple and direct proof of the finite model property (FMP) for CGF and LGF.
PDF of full publication (227 kilobytes)- (need help viewing PDF files?)
BibTEX file for the publication - N.B.
- Conditions for downloading publications from this site.
pubs.doc.ic.ac.uk: built & maintained by Ashok Argent-Katwala.