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
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history
Request removal from index
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 26,692
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.

Monthly downloads

Added to index

2009-01-28

Total downloads

15 ( #311,282 of 2,158,435 )

Recent downloads (6 months)

5 ( #64,770 of 2,158,435 )

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Order:
There  are no threads in this forum
Nothing in this forum yet.

Other forums