Finite satisfiability for two‐variable, first‐order logic with one transitive relation is decidable

Mathematical Logic Quarterly 64 (3):218-248 (2018)
  Copy   BIBTEX

Abstract

We consider two‐variable, first‐order logic in which a single distinguished predicate is required to be interpreted as a transitive relation. We show that the finite satisfiability problem for this logic is decidable in triply exponential non‐deterministic time. Complexity falls to doubly exponential non‐deterministic time if the transitive relation is constrained to be a partial order.

Categories

Add categories

Keywords

Reprint years

DOI

10.1002/malq.201700055

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,202

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Two variable first-order logic over ordered domains.Martin Otto - 2001 - Journal of Symbolic Logic 66 (2):685-702.
Two Variable First-Order Logic Over Ordered Domains.Martin Otto - 2001 - Journal of Symbolic Logic 66 (2):685-702.
The guarded fragment with transitive guards.Wiesław Szwast & Lidia Tendera - 2004 - Annals of Pure and Applied Logic 128 (1-3):227-276.
Undecidability results on two-variable logics.Erich Grädel, Martin Otto & Eric Rosen - 1999 - Archive for Mathematical Logic 38 (4-5):313-354.
Decidable fragments of first-order temporal logics.Ian Hodkinson, Frank Wolter & Michael Zakharyaschev - 2000 - Annals of Pure and Applied Logic 106 (1-3):85-134.
Complexity of the two-variable fragment with counting quantifiers.Ian Pratt-Hartmann - 2005 - Journal of Logic, Language and Information 14 (3):369-395.
Computability of validity and satisfiability in probability logics over finite and countable models.Greg Yang - 2015 - Journal of Applied Non-Classical Logics 25 (4):324-372.
Decidable fragments of first-order modal logics.Frank Wolter & Michael Zakharyaschev - 2001 - Journal of Symbolic Logic 66 (3):1415-1438.
On the Decision Problem for Two-Variable First-Order Logic.Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.
On the decision problem for two-variable first-order logic.Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi - 1997 - Bulletin of Symbolic Logic 3 (1):53-69.
Decidable Fragments of First-Order Modal Logics.Frank Wolter & Michael Zakharyaschev - 2001 - Journal of Symbolic Logic 66 (3):1415-1438.
On the restraining power of guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
On the Restraining Power of Guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
An Event-Based Fragment of First-Order Logic over Intervals.Savas Konur - 2011 - Journal of Logic, Language and Information 20 (1):49-68.
On the computational complexity of the numerically definite syllogistic and related logics.Ian Pratt-Hartmann - 2008 - Bulletin of Symbolic Logic 14 (1):1-28.

Analytics

Added to PP
2018-07-26

Downloads
8 (#1,249,165)

6 months
2 (#1,157,335)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The fluted fragment with transitive relations.Ian Pratt-Hartmann & Lidia Tendera - 2022 - Annals of Pure and Applied Logic 173 (1):103042.

Add more citations

References found in this work

Two variable first-order logic over ordered domains.Martin Otto - 2001 - Journal of Symbolic Logic 66 (2):685-702.

Add more references