THE EXPRESSIVE POWER OF FINITELY MANY GENERALIZED QUANTIFIERS

We consider extensions of first order logic [FO] and fixed point logic (FP) by means of generalized quantifiers in the sense of Lindstrom. W e show that adding a finite set of such quantifiers to FP fails to cap ture PTIME, even over a fixed signature, strengthening earlier results . We also prove a stronger version of this result for PSPACE, which en ables us to establish that PSPACE not equal FO on any infinite class o f ordered structures, a weak version of the ordered conjecture formula ted by Ph. G. Kolaitis and M. Y. Vardi (Fixpoint logic vs. infinitary logic in finite-model theory, in ''Proceedings, 7th IEEE Symposium on Logic in Computer Science, 1992,'' pp. 46-57). These results are obtai ned by defining a notion of element type for bounded variable logics w ith finitely many generalized quantifiers. Using these, we characteriz e the classes of finite structures over which the infinitary logic L(p roportional to omega)(omega) extended by a finite aw set of generalize d quantifiers Q is no more expressive than first order logic extended by the quantifiers in Q. (C) 1995 Academic Press. Inc.