Paper: Relativized Logspace and Generalized Quantifiers Over Finite Structures (at LICS 1995)
Authors: Georg GottlobAbstract
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 Symp. on Logic in Computer Science, {LICS} 1995}, year = 1995, editor = {Dexter Kozen}, month = {June}, pages = {65-78}, location = {San Diego, CA, USA}, publisher = {IEEE Computer Society Press} }