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

**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} }