Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-08T04:26:43.806Z Has data issue: false hasContentIssue false
  • English
  • Français

Fluted formulas and the limits of decidability

Published online by Cambridge University Press:  12 March 2014

William C. Purdy
William C. Purdy*
Affiliation:
School of Computer and Information Science, Syracuse University, Syracuse, NY 13244-4100, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 61 , Issue 2 , June 1996 , pp. 608 - 620
Copyright
Copyright © Association for Symbolic Logic 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Andrews, Peter B., An introduction to mathematical logic and type theory, Academic Press, Orlando, 1986.Google Scholar
[2]Arbib, Michael A., Kfoury, A. J., and Moll, Robert N., A basis for theoretical computer science, Springer-Verlag, New York, 1981.Google Scholar
[3]Enderton, Herbert B., A mathematical introduction to logic, Academic Press, New York, 1972.Google Scholar
[4]Gallier, Jean H., Logic for computer science, Harper & Row, New York, 1986.Google Scholar
[5]Grätzer, George, General lattice theory, Academic Press, New York, 1978.Google Scholar
[6]Hintikka, Jaakko, Surface information and depth information, Information and inference (Hintikka, J. and Suppes, P., editors), D. Reidel Publishing Company, Dordrecht, 1970, pp. 263–297.Google Scholar
[7]Hintikka, Jaakko, Logic, language-games and information, Clarendon Press, Oxford, 1973.Google Scholar
[8]Huet, Gerard, A uniform approach to type theory, Logical foundations of logical programming (Huet, Gerard, editor), Addison Wesley Publishing Company, Reading, Massachusetts, 1990, pp. 337–397.Google Scholar
[9]Noah, Aris, Predicate-functors and the limits of decidability in logic, Notre Dame Journal of Formal Logic, vol. 21 (1980), pp. 701–707.Google Scholar
[10]Purdy, W. C., A logic for natural language, Notre Dame Journal of Formal Logic, vol. 32 (1991), pp. 409–425.Google Scholar
[11]Purdy, W. C., A variable-free logic for anaphora, Patrick Suppes: Scientific philosopher (Humphreys, P., editor), Kluwer Academic Publishers, Dordrecht, 1994, pp. 41–70.Google Scholar
[12]Quine, W. V., Variables explained away, Proceedings of the American Philosophical Society, vol. 104 (1960), pp. 343–347.Google Scholar
[13]Quine, W. V., On the limits of decision, Proceedings of the 14th international congress of philosophy (University of Vienna), vol. 3, 1969, also in W. V. Quine Theories and things, Harvard University Press, Cambridge, 1981, pp. 157–163.Google Scholar
[14]Quine, W. V., The ways of paradox and other essays, enlarged ed., Harvard University Press, Cambridge, 1976.Google Scholar
[15]Quine, W. V., Predicate functors revisited, this Journal, vol. 46 (1981), pp. 649–652.Google Scholar
[16]Quine, W. V., Methods of logic, fourth ed., Harvard University Press, Cambridge, 1982.Google Scholar
[17]Rantala, Veikko, Constituents, Jaakko hintikka (Bogdan, Radu J., editor), D. Reidel Publishing Company, Dordrecht, 1987, pp. 43–76.Google Scholar
[18]Sommers, Fred, The calculus of terms, The new syllogistic (Englebretsen, George, editor), Peter Lang, New York, 1987, pp. 11–56.Google Scholar
[19]Stickel, Mark E., Schubert's steamroller problem: Formulations and solution, Journal of Automated Reasoning, vol. 2 (1986), pp. 89–101.Google Scholar
[20]Suppes, Patrick, Variable-free semantics with remarks on procedural extensions, Language, mind, and brain (Simmon, and Scholes, , editors), Lawrence Erlbaum Associates, New Jersey, 1982, pp. 21–34.Google Scholar