RELATIVIZED LOGSPACE AND GENERALIZED QUANTIFIERS OVER FINITE ORDERED STRUCTURES

We here examine the expressive power of first order logic with general ized quantifiers over finite ordered structures. In particular, we add ress the following problem: Given a family Q of generalized quantifier s expressing a complexity class C, what is the expressive power of fir st 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., log arithmic space relativized to an oracle in C. We show that this is not always true. However, after studying the problem from a general point of view, we derive sufficient conditions on C such that FO(Q) capture s L-C. These conditions are fulfilled by a large number of relevant co mplexity 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 [Ann. Pure Appl. Logic, vol. 32, 1986]. Furthermore we show that for many Families Q of generalized quantifiers (including the fam ily of Henkin quantifiers), each FO(Q)-formula can be replaced by an e quivalent FO(Q)-formula with only two occurrences of generalized quant ifiers. This generalizes and extends an earlier normal-form result by I. A. Stewart [Fundamenta Inform. vol. 18, 1993].