Fluted formulas and the limits of decidability

Journal of Symbolic Logic 61 (2):608-620 (1996)
  Copy   BIBTEX

Abstract

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 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

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

Analytics

Added to PP
2009-01-28

Downloads
101 (#166,227)

6 months
11 (#191,387)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

More Fragments of Language.Ian Pratt-Hartmann & Allan Third - 2006 - Notre Dame Journal of Formal Logic 47 (2):151-177.
Decidability of Fluted Logic with Identity.William C. Purdy - 1996 - Notre Dame Journal of Formal Logic 37 (1):84-104.
The fluted fragment with transitive relations.Ian Pratt-Hartmann & Lidia Tendera - 2022 - Annals of Pure and Applied Logic 173 (1):103042.
Inexpressiveness of First-Order Fragments.William C. Purdy - 2006 - Australasian Journal of Logic 4 (5):1-12.

Add more citations

References found in this work

The Ways of Paradox and Other Essays.Yehoshua Bar-Hillel - 1967 - Philosophy and Phenomenological Research 28 (4):596-600.
Variables Explained Away.Willard V. Quine - 1960 - Journal of Symbolic Logic 32 (1):112-112.
Methods of Logic.A. R. Turquette & Willard Van Orman Quine - 1951 - Journal of Symbolic Logic 16 (4):268.
Surface Information and Depth Information.Jaakko Hintikka - 1970 - In Jaakko Hintikka & O. Suppes (eds.), Information and Inference. Dordrecht: Reidel.
The calculus of terms.Fred Sommers - 1970 - Mind 79 (313):1-39.

View all 9 references / Add more references