Fluted formulas and the limits of decidability
Journal of Symbolic Logic 61 (2):608-620 (1996)
| 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 | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,672 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesMakoto Tatsuta (1993). Uniqueness of Normal Proofs of Minimal Formulas. Journal of Symbolic Logic 58 (3):789-799.
M. Marshall (2006). Local-Global Properties of Positive Primitive Formulas in the Theory of Spaces of Orderings. Journal of Symbolic Logic 71 (4):1097 - 1107.
Andrew M. Pitts (1992). On an Interpretation of Second Order Quantification in First Order Intuitionistic Propositional Logic. Journal of Symbolic Logic 57 (1):33-52.
Frank Wolter & Michael Zakharyaschev (2001). Decidable Fragments of First-Order Modal Logics. Journal of Symbolic Logic 66 (3):1415-1438.
Stål O. Aanderaa, Egon Börger & Harry R. Lewis (1982). Conservative Reduction Classes of Krom Formulas. Journal of Symbolic Logic 47 (1):110-130.
Giorgie Dzhaparidze (1990). Decidable and Enumerable Predicate Logics of Provability. Studia Logica 49 (1):7 - 21.
William C. Purdy (1996). Decidability of Fluted Logic with Identity. Notre Dame Journal of Formal Logic 37 (1):84-104.
William C. Purdy (1999). Quine's 'Limits of Decision'. Journal of Symbolic Logic 64 (4):1439-1466.
William C. Purdy (2002). Complexity and Nicety of Fluted Logic. Studia Logica 71 (2):177 - 198.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
