Fluted Logic is essentially first-order predicate logic deprived of variables. The lack of variables results in reduced expressiveness. Nevertheless, many logical problems that can be stated in natural language, such as the famous Schubert's Steamroller, can be rendered in fluted logic. Further evidence of the expressiveness of fluted logic is its close relation to description logics. Already it has been shown that fluted logic is decidable and has the finite-model property. This (...) paper shows that fluted logic has the exponential-model property and that deciding satisfiability is NEXPTIME-complete. It is shown further that fluted logic is 'nice, that is, it shares with first-order predicate logic the interpolation property and model preservation properties. (shrink)

Fluted Logic is essentially first-order predicate logic deprived of variables. The lack of variables results in reduced expressiveness. Nevertheless, many logical problems that can be stated in natural language, such as the famous Schubert's Steamroller, can be rendered in fluted logic. Further evidence of the expressiveness of fluted logic is its close relation to description logics. Already it has been shown that fluted logic is decidable and has the finite-model property. This (...) paper shows that fluted logic has the exponential-model property and that deciding satisfiability is NEXPTIME-complete. It is shown further that fluted logic is 'nice’, that is, it shares with first-order predicate logic the interpolation property and model preservation properties. (shrink)

Fluted logic is the restriction of pure predicate logic to formulas in which variables play no essential role. Although fluted logic is significantly weaker than pure predicate logic, it is of interest because it seems closely to parallel natural logic, the logic that is conducted in natural language. It has been known since 1969 that if conjunction in fluted formulas is restricted to subformulas of equal arity, satisfiability is decidable. However, the (...) decidability of sublogics lying between this restricted (homogeneous) fluted logic and full predicate logic remained unknown. In 1994 it was shown that the satisfiability of fluted formulas without restriction is decidable, thus reducing the unknown region significantly. This paper further reduces the unknown region. It shows that fluted logic with the logical identity is decidable. Since the reflection functor can be defined in fluted logic with identity, it follows that fluted logic with the reflection functor also lies within the region of decidability. Relevance to natural logic is increased since the identity permits definition of singular predicates, which can represent anaphoric pronouns. (shrink)

The fluted fragment is a fragment of first-order logic (without equality) in which, roughly speaking, the order of quantification of variables coincides with the order in which those variables appear as arguments of predicates. It is known that this fragment has the finite model property. We consider extensions of the fluted fragment with various numbers of transitive relations, as well as the equality predicate. In the presence of one transitive relation (together with equality), the finite model property (...) is lost; nevertheless, we show that the satisfiability and finite satisfiability problems for this extension remain decidable. We also show that the corresponding problems in the presence of two transitive relations (with equality) or three transitive relations (without equality) are undecidable, even for the two-variable sub-fragment. (shrink)

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$. (shrink)

In the predicate calculus, variables provide a flexible indexing service which selects the actual arguments to a predicate letter from among possible arguments that precede the predicate letter (in the parse of the formula). In the process of selection, the possible arguments can be permuted, repeated (used more than once), and skipped. If this service is withheld, so that arguments must be the immediately preceding ones, taken in the order in which they occur, the formula is said to be (...) class='Hi'>fluted. Quine showed that if a fluted formula contains only homogeneous conjunction (conjoins only subformulas of equal arity), then the satisfiability of the formula is decidable. It remained an open question whether the satisfiability of a fluted formula without this restriction is decidable. This paper answers that question. (shrink)

A sentence of first-order logic is satisfiable if it is true in some structure, and finitely satisfiable if it is true in some finite structure. The question arises as to whether there exists an algorithm for determining whether a given formula of first-order logic is satisfiable, or indeed finitely satisfiable. This question was answered negatively in 1936 by Church and Turing (for satisfiability) and in 1950 by Trakhtenbrot (for finite satisfiability).In contrast, the satisfiability and finite satisfiability problems are (...) algorithmically solvable for restricted subsets---or, as we say, fragments---of first-order logic, a fact which is today of considerable interest in Computer Science. This book provides an up-to-date survey of the principal axes of research, charting the limits of decision in first-order logic and exploring the trade-off between expressive power and complexity of reasoning. Divided into three parts, the book considers for which fragments of first-order logic there is an effective method for determining satisfiability or finite satisfiability. Furthermore, if these problems are decidable for some fragment, what is their computational complexity? Part I focusses on fragments defined by restricting the set of available formulas. Topics covered include the Aristotelian syllogistic and its relatives, the two-variable fragment, the guarded fragment, the quantifier-prefix fragments and the fluted fragment. Part II investigates logics with counting quantifiers. Starting with De Morgan's numerical generalization of the Aristotelian syllogistic, we proceed to the two-variable fragment with counting quantifiers and its guarded subfragment, explaining the applications of the latter to the problem of query answering in structured data. Part III concerns logics characterized by semantic constraints, limiting the available interpretations of certain predicates. Taking propositional modal logic and graded modal logic as our cue, we return to the satisfiability problem for two-variable first-order logic and its relatives, but this time with certain distinguished binary predicates constrained to be interpreted as equivalence relations or transitive relations. The work finishes, slightly breaching the bounds of first-order logic proper, with a chapter on logics interpreted over trees. (shrink)

I read Stefan Collini’s What are Universities For? last week with very mixed feelings. In the past, I’ve much admired his polemical essays on the REF, “impact”, the Browne Report, etc. in the London Review of Books and elsewhere: they speak to my heart. If you don’t know those essays, you can get some of their flavour from his latest article in the Guardian yesterday. But I found the book a disappointment. Perhaps the trouble is that Collini is too decent, (...) too high-minded, has too unrealistically exalted a view about what actually happens in universities which is too coloured by attitudes appropriate to the traditional humanities. And he is optimistic to the point of fantasy if he thinks that people are so susceptible to “the romance of ideas and the power of beauty” that they will want, or can be brought to want, lots and lots of universities in order to promote the ideas (as if they would suppose that the task of “conserving, understanding, extending and handing on to subsequent generations the intellectual, scientific, and artistic heritage of mankind” was clearly ill-served when there were only forty universities in England, as opposed to a hundred and whatever). (shrink)

A common reaction to Hegel’s suggestion that we collapse Kant’s distinction between form and content is that, since such a move would also deprive us of any way of distinguishing the merely logical from the real possibility of our concepts, it is incoherent and ought to be rejected. It is true that these two distinctions are intimately related in Kant, such that if one goes, the other does as well. But it is less obvious that giving them up as Kant (...) conceives them is as incoherent a proposal as many of Hegel’s critics think. It has been the point of a recent account of Hegel’s idealism to demonstrate that his critique of Kant’s dichotomy between form and content or concept and intuition does not commit him to the view that human cognition is materially creative of its content in the manner of a God-like or intuitive intellect—does not, in other words, signify a return to a pre-Critical metaphysics. This is the interpretative stance I adopt here as well, in hope of giving defenders of Kant reasons for taking Hegel more seriously. (shrink)