Paper: Relativized Logspace and Generalized Quantifiers Over Finite Structures (at LICS 1995)

Authors: Georg Gottlob

Abstract

The expressive power of first order logic with generalized quantifiers over finite ordered structures is studied. The following problem is addressed: Given a family Q of generalized quantifiers expressing a complexity class C, what is the expressive power of first order logic FO(Q) extended by the quantifiers in Q? From previously studied examples, one would expect that FO(Q) captures L^C, i.e., logarithmic space relativized by an oracle in C. We show that this is not always true. However, we derive sufficient conditions on complexity class C such that FO(Q) captures L^C. These conditions are fulfilled by a large number of relevant complexity classes, in particular, for example, by NP. As an application of this result, it follows that first order logic extended by Henkin quantifiers captures L^{NP}. This answers a question raised by Blass and Gurevich. Furthermore, we show that for many families Q of generalized quantifiers (including the family of Henkin quantifiers), each FO(Q) formula can be replaced by an equivalent FO(Q) formula with only two occurrences of generalized quantifiers.

BibTeX

  @InProceedings{Gottlob-RelativizedLogspace,
    author = 	 {Georg Gottlob},
    title = 	 {Relativized Logspace and Generalized Quantifiers Over Finite Structures},
    booktitle =  {Proceedings of the Tenth Annual IEEE Symposium on Logic in Computer Science (LICS 1995)},
    year =	 {1995},
    month =	 {June}, 
    pages =      {65--78},
    location =   {San Diego, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }