Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-24T13:51:28.536Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Decision Problem for Two-Variable First-Order Logic

Published online by Cambridge University Press:  15 January 2014

Erich Grädel ,
Phokion G. Kolaitis  and
Moshe Y. Vardi
Erich Grädel
Affiliation:
Lehrgebiet Mathematische Grundlagen Der Informatik Rwth Aachen, D-52056 Aachen, Germany, E-mail: [email protected], URL: http://www.informatik.rwth-aachen.de/WWW-math/index.html
Phokion G. Kolaitis
Affiliation:
Computer Science Department, University of California, Santa Cruz, CA 95064, USA, E-mail: [email protected]
Moshe Y. Vardi
Affiliation:
Department of Computer Science, Rice University, Houston, TX 77005-1892, USA, E-mail: [email protected], URL: http://www.cs.rice.edu/~vardi
Get access Rights & Permissions [Opens in a new window]

Abstract

We identify the computational complexity of the satisfiability problem for FO2, the fragment of first-order logic consisting of all relational first-order sentences with at most two distinct variables. Although this fragment was shown to be decidable a long time ago, the computational complexity of its decision problem has not been pinpointed so far. In 1975 Mortimer proved that FO2 has the finite-model property, which means that if an FO2-sentence is satisiable, then it has a finite model. Moreover, Mortimer showed that every satisfiable FO2-sentence has a model whose size is at most doubly exponential in the size of the sentence. In this paper, we improve Mortimer's bound by one exponential and show that every satisfiable FO2-sentence has a model whose size is at most exponential in the size of the sentence. As a consequence, we establish that the satisfiability problem for FO2 is NEXPTIME-complete.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 3 , Issue 1 , March 1997 , pp. 53 - 69
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] van Benthem, J. F. A. K., Modal correspondence theory, Ph.D. thesis , University of Amsterdam, 1976.Google Scholar
[2] van Benthem, J. F. A. K., Modal logic and classical logic, Bibliopolis, Naples, 1985.Google Scholar
[3] van Benthem, J. F. A. K., Temporal logic, Report x-91-05, Institute for Logic, Language, and Computation, University of Amsterdam, 1991.Google Scholar
[4] Bernays, P. and Schönfinkel, M., Zum Entscheidungsproblem der mathematischen Logik, Mathematische Annalen, vol. 99 (1928), pp. 342–372.CrossRefGoogle Scholar
[5] Bochmann, G. V., Hardware specification with temporal logic: an example, IEEE Transactions on Computers, vol. C-31 (1982), pp. 223–231.Google Scholar
[6] Börger, E., Grädel, E., and Gurevich, Y., The classical decision problem, Springer-Verlag, 1997.Google Scholar
[7] Brafman, R., Latombe, J.-C., Moses, Y., and Shoham, Y., Knowledge as a tool in motion planning under uncertainty, Theoretical aspects of reasoning about knowledge: Proceedings fifth conference (Fagin, R., editor), Morgan Kaufmann, San Francisco, California, 1994, pp. 208–224.CrossRefGoogle Scholar
[8] Burrows, M., Abadi, M., and Needham, R., Authetication: a practical study in belief and action, Proceedings of the 2nd conference on theoretical aspects of reasoning about knowledge, 1988, pp. 325–342.Google Scholar
[9] Cai, J., Fürer, M., and Immerman, N., An optimal lower bound on the number of variables for graph identification, Combinatorica, vol. 12 (1992), pp. 389–410.CrossRefGoogle Scholar
[10] Castilho, J. M. V., Casanova, M. A., and Furtado, A. L., A temporal framework for database specification, Proceedings of the 8th international conference on very large data bases, 1982, pp. 280–291.Google Scholar
[11] Chellas, B. F., Modal logic, Cambridge University Press, Cambridge, U.K., 1980.CrossRefGoogle Scholar
[12] Church, A., A note on the Entscheidungsproblem, Journal of Symbolic Logic, vol. 1 (1936), pp. 101–102.Google Scholar
[13] Clarke, E. M., Emerson, E. A., and Sistla, A. P., Automatic verification of finite-state concurrent systems using temporal logic specifications, ACM Transactions on Programming Languages and Systems, vol. 8 (1986), no. 2, pp. 244–263, an early version appeared in Proceedings of the 10th ACM symposium on principles of programming languages , 1983.Google Scholar
[14] Dawar, A., Lindell, S., and Weinstein, S., Infinitary logic and inductive definability over finite structures, Information and Computation, vol. 119 (1995), pp. 160–175.Google Scholar
[15] Dreben, B. and Goldfarb, W. D., The decision problem: Solvable classes of quantificational formulas, Addison-Wesley, 1979.Google Scholar
[16] Feferman, S., Dawson, J. jr., Kleene, S., Moore, G., Solovay, R.,, and van Heijenoort, J. (editors), K. Gödel, collected works, volume I: Publications 1929–1936, Oxford University Press, 1986.Google Scholar
[17] Fischer, M. J. and Ladner, R. E., Propositional dynamic logic of regular programs, Journal of Computer and System Sciences, vol. 18 (1979), no. 2, pp. 194–211.Google Scholar
[18] Fürer, M., Alternation and the Ackermann case of the decision problem, L'Enseignment Mathematique, vol. 27 (1981), pp. 137–162.Google Scholar
[19] Fürer, M., The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems), Logical machines: Decision problems and complexity, Lecture Notes in Computer Science, vol. 171, Springer-Verlag, 1981, pp. 312–319.CrossRefGoogle Scholar
[20] Gabbay, D., Expressive functional completeness in tense logic, Aspects of philosophical logic (Mönnich, U., editor), Reidel, 1971, pp. 91–117.Google Scholar
[21] Gödel, K., Ein Spezialfall des Entscheidungsproblems der theoretischen Logik, Ergebnisse der Mathematik Kolloq., vol. 2 (1932), pp. 27–28, reprinted and translated in [16, pp. 230–233].Google Scholar
[22] Gödel, K., Zum Entscheidungsproblem des logischen Funktionenkalküls, Monatshefte für Mathematik Phys., vol. 40 (1933), pp. 433–443, reprinted and translated in [16, pp. 306–326].Google Scholar
[23] Goldfarb, W., The unsolvability of the Gödel class with identity, Journal of Symbolic Logic, vol. 49 (1984), pp. 1237–1252.Google Scholar
[24] Grädel, E., Complexity of formula classes in first order logic with functions, Fundamentals of computation theory (FCT '89), Lecture Notes in Computer Science, vol. 380, Springer-Verlag, 1989, pp. 224–233.Google Scholar
[25] Grädel, E., Satisfiability of formulae with one ∀ is decidable in exponential time, Archive of Mathematical Logic, vol. 29 (1990), pp. 265–276.Google Scholar
[26] Grädel, E., Otto, M., and Rosen, E., Two-variable logic with counting is decidable, unpublished manuscript, 1996.Google Scholar
[27] Grädel, E., Otto, M., and Rosen, E., Undecidability results for two-variable logics, unpublished manuscript, 1996.Google Scholar
[28] Halpern, J. Y. and Moses, Y., Knowledge and common knowledge in a distributed environment, Journal of the ACM, vol. 37 (1990), no. 3, pp. 549–587, a preliminary version appeared in Proceedings of the 3rd ACM symposium on principles of distributed computing , 1984.Google Scholar
[29] Halpern, J. Y. and Moses, Y., A guide to completeness and complexity for modal logics of knowledge and belief, Artificial Intelligence, vol. 54 (1992), pp. 319–379.Google Scholar
[30] Henkin, L., Logical systems containing only a finite number of symbols, Report, Department of Mathematics, University of Montreal, 1967.Google Scholar
[31] Hodges, W., Model theory, Cambridge University Press, 1993.Google Scholar
[32] Hopcroft, J. E. and Ullman, J. D., Introduction to automata theory, languages and computation, Addison-Wesley, New York, 1979.Google Scholar
[33] Immerman, N., Upper and lower bounds for first-order expressibility, Journal of Computer and System Sciences, vol. 25 (1982), pp. 76–98.Google Scholar
[34] Immerman, N., Dspace[nk ] = var[k + 1], Proceedings of the 6th IEEE symposium on structure in complexity theory, 1991, pp. 334–340.Google Scholar
[35] Immerman, N. and Kozen, D., Definability with bounded number of bound variables, Information and Computation, vol. 83 (1989), pp. 121–139.Google Scholar
[36] Kalmár, L., Über die Erfüllbarkeit derjenigen Zählhausdrücke, welche in der Normalform zwei benachbarte Allzeichen enthalten, Mathematische Annalen, vol. 108 (1933), pp. 466–484.Google Scholar
[37] Kolaitis, Ph. G. and Vardi, M. Y., 0-1 laws and decision problems for fragments of second-order logic, Information and Computation, vol. 87 (1990), pp. 302–338.Google Scholar
[38] Kolaitis, Ph. G. and Vardi, M. Y., Infinitary logic and 0-1 laws, Information and Computation, vol. 98 (1992), pp. 258–294.CrossRefGoogle Scholar
[39] Kolaitis, Ph. G. and Vardi, M. Y., On the expressive power of Datalog: tools and a case study, Journal of Computer and System Sciences, vol. 51 (1995), no. 1, pp. 110–134.Google Scholar
[40] Ladner, R. E., The computational complexity of provability in systems of modal propositional logic, SIAM Journal on Computing, vol. 6 (1977), no. 3, pp. 467–480.Google Scholar
[41] Lewis, H. R., Unsolvable classes of quantificational formulas, Addison-Wesley, 1979.Google Scholar
[42] Lewis, H. R., Complexity results for classes of quantificational formulas, Journal of Computer and System Sciences, vol. 21 (1980), pp. 317–353.Google Scholar
[43] Lipski, W., On the logic of incomplete information, Proceedings of the 6th international symposium on mathematical foundations of computer science, Lecture Notes in Computer Science, vol. 53, Springer-Verlag, Berlin/New York, 1977, pp. 374–381.Google Scholar
[44] McCarthy, J. and Hayes, P. J., Some philosophical problems from the standpoint of artificial intelligence, Machine intelligence 4 (Michie, D., editor), Edinburgh University Press, Edinburgh, 1969, pp. 463–502.Google Scholar
[45] Mortimer, M., On language with two variables, Zeit. für Math. Logik und Grund. der Math., vol. 21 (1975), pp. 135–140.CrossRefGoogle Scholar
[46] Otto, M., Bounded variable logics and counting—a study in finite models, Habilitationsschrift RWTH, Aachen, 1995, a revised version will appear in Lecture Notes in Logics, Springer-Verlag, 1995.Google Scholar
[47] Pnueli, A., The temporal logic of programs, Proceedings of the 18th IEEE symposium on foundations of computer science, 1977, pp. 46–57.Google Scholar
[48] Pratt, V.R., Semantical considerations on Floyd-Hoare logic, Proceedings of the 17th IEEE symposium on foundations of computer science, 1976, pp. 109–121.Google Scholar
[49] Pratt, V.R., A near optimal method for reasoning about action, Journal of Computer and System Sciences, vol. 20 (1980), pp. 231–254.CrossRefGoogle Scholar
[50] Ramsey, F. P., On a problem in formal logic, Proceedings of the London Mathematical Society, vol. 30 (1928), pp. 264–268.Google Scholar
[51] Reif, J. H. and Sistla, A. P., A multiprocessor network logic with temporal and spatial modalities, Proceedings of the 12th international colloqium on automata, languages, and programming, Lecture Notes in Computer Science, vol. 104, Springer-Verlag, Berlin/New York, 1983.Google Scholar
[52] Schütte, K., Untersuchungen zum Entscheidungsproblem der mathematischen Logik, Mathematische Annalen, vol. 109 (1934), pp. 572–603.Google Scholar
[53] Scott, D., A decision method for validity of sentences in two variables, Journal of Symbolic Logic, vol. 27 (1962), p. 377.Google Scholar
[54] Sistla, A. P. and Clarke, E. M., The complexity of propositional linear temporal logics, Journal of the ACM, vol. 32 (1985), no. 3, pp. 733–749.Google Scholar
[55] Turing, A. M., On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, vol. 42 (1937), pp. 230–265, correction in vol. 43, pp. 544–546.Google Scholar
[56] Vardi, M. Y., On the complexity of bounded-variable queries, Proceedings of the 14th ACM symposium on principles of database systems, 1995, pp. 266–276.Google Scholar
[57] Vardi, M. Y., What makes modal logic so robustly decidable?, Descriptive complexity and finite models, American Mathematical Society, 1997.Google Scholar
[58] Vardi, M. Y. and Wolper, P., Automata-theoretic techniques for modal logic of programs, Journal of Computer and System Sciences, vol. 32 (1986), pp. 183–221.Google Scholar