Complexity and nicety of fluted logic

Studia Logica 71 (2):177 - 198 (2002)

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.
Keywords Philosophy   Logic   Mathematical Logic and Foundations   Computational Linguistics
Categories (categorize this paper)
Reprint years 2004
DOI 10.1023/A:1016596721799
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 46,373
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

The Finite Model Property in Tense Logic.Frank Wolter - 1995 - Journal of Symbolic Logic 60 (3):757-774.
Decidability of Fluted Logic with Identity.William C. Purdy - 1996 - Notre Dame Journal of Formal Logic 37 (1):84-104.
An Event-Based Fragment of First-Order Logic Over Intervals.Savas Konur - 2011 - Journal of Logic, Language and Information 20 (1):49-68.
On the Restraining Power of Guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
Pure Second-Order Logic with Second-Order Identity.Alexander Paseau - 2010 - Notre Dame Journal of Formal Logic 51 (3):351-360.
Fluted Formulas and the Limits of Decidability.William C. Purdy - 1996 - Journal of Symbolic Logic 61 (2):608-620.

Analytics

Added to PP index
2009-01-28

Total views
19 ( #484,789 of 2,286,141 )

Recent downloads (6 months)
2 ( #571,926 of 2,286,141 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature