Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T18:44:33.605Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  15 January 2014

Erich Grädel
Affiliation:
Lehrgebiet Mathematische Grundlagen Der Informatik Rwth Aachen, D-52056 Aachen, Germany, E-mail: graedel@informatik.rwth-aachen.de, 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: kolaitis@cse.ucsc.edu
Moshe Y. Vardi
Affiliation:
Department of Computer Science, Rice University, Houston, TX 77005-1892, USA, E-mail: vardi@cs.rice.edu, URL: http://www.cs.rice.edu/~vardi

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.

Information

Type
Research Article
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.)

Article purchase

Temporarily unavailable