Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Twenty-Third Annual IEEE Symposium on

Logic in Computer Science (LICS 2008)

Paper: Hypergraph Acyclicity and Extension Preservation Theorems (at LICS 2008)

Winner of the Kleene Award in 2008
Authors: David Duris

Abstract

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.

BibTeX

  @InProceedings{Duris-HypergraphAcyclicit,
    author = 	 {David Duris},
    title = 	 {Hypergraph Acyclicity and Extension Preservation Theorems},
    booktitle =  {Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS 2008)},
    year =	 {2008},
    month =	 {June}, 
    pages =      {418--427},
    location =   {Pittsburgh, PA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2017-04-0512:37
Andrzej Murawski