Search

AbstractWe 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$.

The Σ11(∀∃∀) class is the class of all existential second-order sentences whose first-order part is in the prenex form with prefix of the form ∀∃∀. In this paper we prove that every rational number in the interval [0,1] is the asymptotic probability for some Σ11(∀∃∀) sentence. This result completes the classification of asymptotic probabilities for the existential second-order minimal classes.