Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Andréka, Hajnal, Johan van Benthem, and Istvan Németi, 'Modal languages and bounded fragments of predicate logic', Journal of Philosophical Logic 27 (1998), 217-274.
Andréka, Hajnal, Ágnes Kurucz, István Németi, and Ildikó Sain, Applying Algebraic Logic; A General Methodology Mathematical Institute of the Hungarian Academy of Sciences, Budapest, Hungary, 1994.
Andrews, Peter B., An Introduction to Mathematical Logic and Type Theory, Academic Press, Orlando, 1986.
van Benthem, Johan, Exploring Logical Dynamics, CLSI Publications, Stanford, California, 1996.
Grädel, E., P. Kolaitis, and M. Vardi, 'On the decision problem for two-variable first-order logic', Bulletin of Symbolic Logic 3 (1997), 53-69.
Halpern, Joseph Y., and Yoram Moses, 'A guide to completeness and complexity for modal logics of knowledge and belief', Artificial Intelligence 54 (1992), 319-379.
Hintikka, Jaakko, 'Surface information and depth information', in J. Hintikka, and P. Suppes (eds.), Information and Inference, D. Reidel Publishing Company, Dordrecht, 1970, pp. 263-297.
Hintikka, Jaakko, Logic, Language-Games and Information, Clarendon Press, Oxford, 1973.
Hoogland, Eva, and Maarten Marx, 'Interpolation in Guarded Fragments', ILLC preprint, University of Amsterdam, 2000.
Hustadt, U., and R. A. Schmidt, 'Issues of decidability for description logics in the framework of resolution', in R. Caferra and G. Salzer (eds), Automated Deduction in Classical and Non-Classical Logic, Lecture Notes in Artificial Intelligence, 1761, Springer, New York, 2000, pp. 191-205.
Lutz, Carsten and Ulrike Sattler, 'The complexity of reasoning with Boolean modal logics', LTCS-Report 00-02, Aachen University of Technology, Aachen, 2000.
Hans Jürgen Ohlbach and Renate A. Schmidt, 'Functional translation and second-order frame properties of modal logics', Journal of Logic and Computation 7, 1997, 581-603.
Purdy, W. C., 'Fluted formulas and the limits of decidability', Journal of Symbolic Logic 61 (1996), 608-620. This as well as other papers by the author cited here can be obtained by ftp from http://www.cis.syr.edu/~ wcpurdy/.
Purdy, W. C., 'Quine's “Limits of Decision”', Journal of Symbolic Logic 64 (1999), 1439-1466.
Rantala, Veikko, 'Constituents', in J. Bogdan Radu (ed.), Jaakko Hintikka, D. Reidel Publishing Company, Dordrecht, 1987, pp. 43-76.
Schmidt, R. A., 'Decidability by resolution for propositional modal logics', Journal of Automated Reasoning 22, 1999, 379-396.
Schmidt, R. A., and U. Hustadt, 'A resolution decision procedure for fluted logic', in D. McAllester (ed.), Automated Deduction-CADE-17, Lecture Notes in Artificial Intelligence 1831, Springer, New York, 2000, pp. 433-448.
Smullyan, Raymond M., First-Order Logic, Dover Publications, New York, 1995.
Stickel, Mark E., 'Schubert's steamroller problem: Formulations and solutions', Journal of Automated Reasoning 2 (1986), 89-101.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Purdy, W.C. Complexity and Nicety of Fluted Logic. Studia Logica 71, 177–198 (2002). https://doi.org/10.1023/A:1016596721799
Issue Date:
DOI: https://doi.org/10.1023/A:1016596721799