loading...
Hypergraph Acyclicity and Extension Preservation Theorems
June 24-June 27
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2008.122008 23rd Annual IEEE Symposium on Lo ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
A class of structures satisfies the extension preservation theorem if, on this class, every first order sentence is preserved under extension iff it is equivalent to an existential sentence. We consider different acyclicity notions for hypergraphs (\gamma, \beta and \alpha-acyclicity and also acyclicity on hypergraph quotients) and estimate their influence on the validity of the extension preservation theorem on classes of finite structures. More precisely, we prove that \gamma-acyclic classes satisfy the extension preservation theorem, whereas \beta-acyclic classes do not. We also extend the validity of the extension preservation theorem for a generalization of \gamma-acyclicity that we call \gamma-acyclic k-quotient. To achieve this, we make a reduction from finite structures to their k-quotients and we use combinatorial arguments on \gamma-acyclic hypergraphs.
Index Terms:
logic, finite model theory, hypergraph acyclicity, preservation theorems
Citation:
David Duris, "Hypergraph Acyclicity and Extension Preservation Theorems," lics, pp.418-427, 2008 23rd Annual IEEE Symposium on Logic in Computer Science, 2008
Usage of this product signifies your acceptance of the Terms of Use.