Paper: The expressive power of finitely many generalized quantifiers (at LICS 1994)

Authors: Anuj Dawar Lauri Hella

Abstract

We consider extensions of first order logic (FO) and fixed [Bpoint logic (FP) by means of generalized quantifiers in the sense of P. Lindstrom (1966). We show that adding a finite set of such quantifiers to FP fails to capture PTIME, even over a fixed signature. We also prove a stronger version of this result for PSPACE, which enables us to establish a weak version of a conjecture formulated previously by Ph.G. Kolaitis and M.Y. Vardi (1992). These results are obtained by defining a notion of element type for bounded variable logics with finitely many generalized quantifiers. Using these, we characterize the classes of finite structures over which the infinitary logic L_∞w ^w extended by a finite set of generalized quantifiers Q and is no more expressive than first order logic extended by the quantifiers in Q

BibTeX

  @InProceedings{DawarHella-Theexpressivepowero,
    author = 	 {Anuj Dawar and Lauri Hella},
    title = 	 {The expressive power of finitely many generalized quantifiers},
    booktitle =  {Proceedings of the Ninth Annual IEEE Symposium on Logic in Computer Science (LICS 1994)},
    year =	 {1994},
    month =	 {July}, 
    pages =      {20--29},
    location =   {Paris, France}, 
    publisher =	 {IEEE Computer Society Press}
  }