Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-05T17:08:46.395Z Has data issue: false hasContentIssue false
  • English
  • Français

Relativized logspace and generalized quantifiers over finite ordered structures

Published online by Cambridge University Press:  12 March 2014

Georg Gottlob
Georg Gottlob*
Affiliation:
Technische Universität Wien, Institut für Informationssysteme, Paniglgasse 16, A-1040 Wien, Austria, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We here examine the expressive power of first order logic with generalized quantifiers over finite ordered structures. In particular, we address the following problem: 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 LC, i.e., logarithmic 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) captures LC. 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 LNP. 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 family of Henkin quantifiers), each FO(Q)-formula can be replaced by an equivalent FO(Q)-formula with only two occurrences of generalized quantifiers. This generalizes and extends an earlier normal-form result by I. A. Stewart [Fundamenta Inform, vol. 18, 1993].

Keywords

generalized quantifiersHenkin quantifiersfinite model theoryfinite structuresexpressive powercomplexityoraclesrelativizationlogarithmic spacelogspacebounded queries
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 62 , Issue 2 , June 1997 , pp. 545 - 574
Copyright
Copyright © Association for Symbolic Logic 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Balcázar, J., Diaz, J., and Gabarró, J., Structural complexity I, Springer-Verlag, 1988.CrossRefGoogle Scholar
[2]Blass, A. and Gurevich, Y., Henkin quantifiers and complete problems, Annals of Pure and Applied Logic, vol. 32 (1986), pp. 1–16.CrossRefGoogle Scholar
[3]Buss, J., Relativized alternation and space-bounded computation, Journal of Computer and System Sciences, vol. 36 (1988), pp. 351–378.CrossRefGoogle Scholar
[4]Chang, R. and Kadin, J., On computing Boolean connectives of characteristic functions, Mathematical Systems Theory, vol. 28 (1995), no. 3, pp. 173–198.CrossRefGoogle Scholar
[5]Dahlhaus, E., Reductions to NP complete problems by interpretations., Logics and machines, decision problems and complexity, Lecture Notes in Computer Science, vol. 171, Springer-Verlag, 1983.Google Scholar
[6]Dawar, A., Generalized quantifiers and logical reducibilities., Journal of Logic and Computation, vol. 5 (1995), no. 2, pp. 213–226.CrossRefGoogle Scholar
[7]Ebbinghaus, H. D., Extended logics: The general framework, Model-theoretic logics, Perspectives of Mathematical Logic, Ch. 2, Springer-Verlag, 1985.Google Scholar
[8]Ebbinghaus, H. D., Flum, J., and Thomas, W., Mathematical logic, Springer-Verlag, 1980.Google Scholar
[9]Enderton, H., Finite partially ordered quantifiers., Z. Math. Logik, vol. 16 (1970), pp. 393–397.CrossRefGoogle Scholar
[10]Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, Complexity of computation, AMS, 1974, pp. 43–74.Google Scholar
[11]Grädel, E., On logical descriptions of some concepts in structural complexity theory, Proceedings of the 3rd Workshop on Computer Science Logic, CSL'89, Kaiserslautern, FRG, October 2–6, 1989, Lecture Notes in Computer Science, vol. 440, Springer-Verlag, 1990.Google Scholar
[12]Gurevich, Y., Logic and the challenge of computer science, Current trends in theoretical computer science, Computer Science Press, 1988, pp. 1–57.Google Scholar
[13]Hájek, P., Generalized quantifiers and finite sets, Prace Naukowe Instytutu Matematyki Politechniki Wrocławskiej, vol. 14 (1977), pp. 91–104, Proc. of the Autumn School in Set Theory and Hierarchy Theory, Karpacz, Poland, 09, 1974.Google Scholar
[14]Hájek, P. and Havránek, T., Mechanizing hypothesis formation, Springer-Verlag, Berlin, Heidelberg, New York, 1978.CrossRefGoogle Scholar
[15]Hella, L., Definability hierarchies of generalized quantifiers, Annals of Pure and Applied Logic, vol. 43 (1989), pp. 235–271.CrossRefGoogle Scholar
[16]Hella, L., Logical hierarchies in PTIME, Proceedings of the 7th IEEE Symp. on Logic in Computer Science, 1992, pp. 360–368.Google Scholar
[17]Henkin, L., Some remarks on infinitely long formulas, Infinitistic Methods, Proc. of the Symp. on Foundations of Mathematics, Warsaw, Panstwowe, Wydawnictwo, Naukowe and Pergamon Press, 1961, pp. 167–183.Google Scholar
[18]Immerman, N., Languages that capture complexity classes, SIAM Journal on Computing, vol. 16 (1987), pp. 760–778.CrossRefGoogle Scholar
[19]Immerman, N., Nondeterministic space is closed under complementation, SIAM Journal on Computing, vol. 17 (1988), pp. 935–939.CrossRefGoogle Scholar
[20]Johnson, D., A catalog of complexity classes, Handbook of theoretical computer science, vol. I, Chapter 2, Elsevier Science Publishers B.V. (North Holland), 1990, pp. 67–161.Google Scholar
[21]Kolaitis, Ph. G. and Väänänen, J. A., Generalized quantifiers and pebble games on finite structures, Annals of Pure and Applied Logic, vol. 74 (1995), pp. 23–75.CrossRefGoogle Scholar
[22]Ladner, R. and Lynch, N., Relativization of questions about log-space reducibility, Math. Systems Theory, vol. 10 (1976), pp. 19–32.CrossRefGoogle Scholar
[23]Ladner, R., Lynch, N., and Selman, A., A comparison of polynomial-time reducibilities, Theoretical Computer Science, vol. 1 (1975), pp. 103–123.CrossRefGoogle Scholar
[24]Lange, K. J., Nondeterministic log-space reductions, Proceedings of the 11th Symposium on Mathematical Foundations of Computer Science (MFCS'84), Lecture Notes in Computer Science, vol. 176, Springer-Verlag, 1984, pp. 378–388.Google Scholar
[25]Lindström, P., First order predicate logic with generalized quantifiers, Theoria, vol. 32 (1966), pp. 186–195.CrossRefGoogle Scholar
[26]Lindström, P., On extensions of elementary logic, Theoria, vol. 35 (1969), pp. 1–11.CrossRefGoogle Scholar
[27]Lynch, Nancy, Log space machines with multiple oracle tapes, Theoretical Computer Science, vol. 6 (1978), pp. 25–39.CrossRefGoogle Scholar
[28]Makowsky, J. A. and Pnueli, Y. B., Logics capturing complexity classes uniformly, to appear in Logic and Computational Complexity, Leivant, D. (editor), Springer-Verlag, Lecture Notes in Computer Science, Berlin, Heidelberg, New York, 1995.Google Scholar
[29]Makowsky, J. A. and Pnueli, Y. B., Computable quantifiers and logics over finite structures, to appear; preliminary version: TR768, Dept. of Computer Science, Technion—Israel Institute of Technology, Haifa, Israel, 1993.Google Scholar
[30]Makowsky, J. A. and Pnueli, Y. B., Oracles and quantifiers, Computer science logic, refereed papers from csl'93, Lecture Notes in Computer Science, vol. 832, Springer-Verlag, 1994, pp. 198–222.Google Scholar
[31]Nisan, Noam and Ta-Shma, Amnon, Symmetric logspace is closed under complement, Chicago Journal of Theoretical Computer Science, vol. 1995 (1995), article 1.Google Scholar
[32]Ogiwara, Mitsunori, Generalized theorems on relationships among reducibility notions to certain complexity classes, Mathematical Systems Theory, vol. 27 (1994), pp. 189–200.CrossRefGoogle Scholar
[33]Stewart, Iain A., Comparing the expressibility of languages formed using NP-complete operators, Journal of Logic and Computation, vol. 1 (1991), no. 3, pp. 305–330.CrossRefGoogle Scholar
[34]Stewart, Iain A., Complete problems involving Boolean labelled structures and projection transactions, Journal of Logic and Computation, vol. 1 (1991), no. 6, pp. 861–882.CrossRefGoogle Scholar
[35]Stewart, Iain A., Using the Hamilton path operator to capture NP, Journal of Computer and System Sciences, vol. 45 (1992), pp. 127–151.CrossRefGoogle Scholar
[36]Stewart, Iain A., Logical characterization of bounded query classes I: Logspace oracle machines, Fundamenta Informaticae, vol. 18 (1993), pp. 65–92.CrossRefGoogle Scholar
[37]Stewart, Iain A., Logical characterization of bounded query classes II: Polynomial-time oracle machines, Fundamenta Informaticae, vol. 18 (1993), pp. 93–105.CrossRefGoogle Scholar
[38]Szelepcsènyi, R., The method of forced enumeration for nondeterministic automata, Acta Informatica, vol. 26 (1988), pp. 279–284.CrossRefGoogle Scholar
[39]Wagner, Klaus, Bounded query classes, SIAM Journal on Computing, vol. 19 (1990), no. 5, pp. 833–846.CrossRefGoogle Scholar
[40]Walkoe, Wilbur, Finite partially-ordered quantification, this Journal, vol. 35 (1970), pp. 535–555.Google Scholar
[41]Wilson, C. B., Relativized NC, Mathematical Systems Theory, vol. 20 (1987), pp. 13–29.CrossRefGoogle Scholar
[42]Wilson, C. B., On the decomposability of NC and AC, SIAM Journal on Computing, vol. 19 (1990), no. 2, pp. 384–396.CrossRefGoogle Scholar