Two-variable logic: Difference between revisions

Revision as of 16:48, 7 February 2017

Revision as of 21:09, 24 August 2017

Line 4:

== Decidability ==

One of the main points is that someSome important problems about two-variable logic, such as [[satisfiability (logics)|satisfiability]] and [[finite satisfiability (logics)|finite satisfiability]], are [[decidability (computer science)|decidable]].<ref>E. Grädel, P.G. Kolaitis and M. Vardi, "On the Decision Problem for Two-Variable First-Order Logic," The Bulletin of Symbolic Logic, Vol.

3, No. 1 (Mar., 1997), pp. 53-69.</ref> This result generalizes results about the decidability of fragments of two-variable logic, such as certain [[description logic]]s; however, some fragments of two-variable logic enjoy a much lower [[Computational complexity theory|computational complexity]] for their satisfiability problems.