Hostname: page-component-7b7567c8c-m6dxt Total loading time: 0 Render date: 2026-11-19T04:57:21.549Z Has data issue: false hasContentIssue false

THE FLUTED FRAGMENT REVISITED

Published online by Cambridge University Press:  06 June 2019

IAN PRATT-HARTMANN
Affiliation:
SCHOOL OF COMPUTER SCIENCE MANCHESTER UNIVERSITY MANCHESTER, M13 9PL, UK and INSTYTUT INFORMATYKI UNIWERSYTET OPOLSKI 45-040 OPOLE, POLAND E-mail: ipratt@cs.man.ac.uk
WIESŁAW SZWAST
Affiliation:
INSTYTUT INFORMATYKI UNIWERSYTET OPOLSKI 45-040 OPOLE, POLANDE-mail: szwast@math.uni.opole.pl
LIDIA TENDERA
Affiliation:
INSTYTUT INFORMATYKI UNIWERSYTET OPOLSKI 45-040 OPOLE, POLANDE-mail: tendera@math.uni.opole.pl
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 ($m - 2$)-tuply exponential size, whence the satisfiability (= finite satisfiability) problem for this fragment is in ($m - 2$)-NExpTime. Together with other, known, complexity results, this provides tight complexity bounds for ${\cal F}{{\cal L}^m}$ for all $m \le 4$.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2019