First-order logic with two variables and unary temporal logic
Authors:
- M.Y. VardiMVM.Y. Vardi
- T. WilkeTWT. Wilke
- 22 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10436871,p. 228-235
Abstract
We investigate the power of first-order logic with only two variables over /spl omega/-words and finite words, a logic denoted by FO/sup 2/. We prove that FO/sup 2/ can express precisely the same properties as linear temporal logic with only the unary temporal operators: "next", "previously", "sometime in the future", and "sometime in the past", a logic we denote by unary-TL. Moreover, our translation from FO/sup 2/ to unary-TL converts every FO/sup 2/ formula to an equivalent unary-TL formula that is at most exponentially larger, and whose operator depth is at most twice the quantifier depth of the first-order formula. We show that this translation is optimal. While satisfiability for full linear temporal logic, as well as for unary-TL, is known to be PSPACE-complete, we prove that satisfiability for FO/sup 2/ is NEXP-complete, in sharp contrast to the fact that satisfiability for FO/sup 3/ has non-elementary computational complexity. Our NEXP time upper bound for FO/sup 2/ satisfiability has the advantage of being in terms of the quantifier depth of the input formula. It is obtained using a small model property for FO/sup 2/ of independent interest, namely: a satisfiable FO/sup 2/ formula has a model whose "size" is at most exponential in the quantifier depth of the formula. Using our translation from FO/sup 2/ to unary-TL we derive this small model property from a corresponding small model property for unary-TL. Our proof of the small model property for unary-TL is based on an analysis of unary-TL types.Keywords
This publication has 12 references indexed in Scilit:
- On the Decision Problem for Two-Variable First-Order LogicThe Bulletin of Symbolic Logic, 1997
- Reasoning about Infinite ComputationsInformation and Computation, 1994
- Temporal Logic1994
- Definability with bounded number of bound variablesInformation and Computation, 1989
- The complexity of propositional linear temporal logicsJournal of the ACM, 1985
- The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems)Lecture Notes in Computer Science, 1984
- Complexity results for classes of quantificational formulasJournal of Computer and System Sciences, 1980
- On the temporal analysis of fairness1980
- The temporal logic of programs1977
- On languages with two variablesMathematical Logic Quarterly, 1975