The fluted fragment revisited

Journal of Symbolic Logic 84 (3):1020-1048 (2019)
  Copy   BIBTEX

Abstract

We study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, motivated by the work of W. V. Quine. We show that the satisfiability problem for this fragment has nonelementary complexity, thus refuting an earlier published claim by W. C. Purdy that it is in NExpTime. More precisely, we consider ${\cal F}{{\cal L}^m}$, the intersection of the fluted fragment and the m-variable fragment of first-order logic, for all $m \ge 1$. We show that, for $m \ge 2$, this subfragment forces $\left\lfloor {m/2} \right\rfloor$-tuply exponentially large models, and that its satisfiability problem is $\left\lfloor {m/2} \right\rfloor$-NExpTime-hard. We further establish that, for $m \ge 3$, any satisfiable ${\cal F}{{\cal L}^m}$-formula has a model of at most -tuply exponential size, whence the satisfiability problem for this fragment is in -NExpTime. Together with other, known, complexity results, this provides tight complexity bounds for ${\cal F}{{\cal L}^m}$ for all $m \le 4$.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,593

External links

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

Through your library

Similar books and articles

Complexity and nicety of fluted logic.William C. Purdy - 2002 - Studia Logica 71 (2):177 - 198.
Complexity and Nicety of Fluted Logic.William C. Purdy - 2002 - Studia Logica 71 (2):177-198.
The guarded fragment with transitive guards.Wiesław Szwast & Lidia Tendera - 2004 - Annals of Pure and Applied Logic 128 (1-3):227-276.
An Event-Based Fragment of First-Order Logic over Intervals.Savas Konur - 2011 - Journal of Logic, Language and Information 20 (1):49-68.
Complexity of the two-variable fragment with counting quantifiers.Ian Pratt-Hartmann - 2005 - Journal of Logic, Language and Information 14 (3):369-395.
Complexity Results of STIT Fragments.François Schwarzentruber - 2012 - Studia Logica 100 (5):1001-1045.
Fragments of language.Ian Pratt-Hartmann - 2004 - Journal of Logic, Language and Information 13 (2):207-223.
Fluted formulas and the limits of decidability.William C. Purdy - 1996 - Journal of Symbolic Logic 61 (2):608-620.
On the Restraining Power of Guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
Decidability of Fluted Logic with Identity.William C. Purdy - 1996 - Notre Dame Journal of Formal Logic 37 (1):84-104.
On the restraining power of guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.

Analytics

Added to PP
2019-09-18

Downloads
8 (#1,138,312)

6 months
2 (#668,348)

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

No references found.

Add more references