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 | 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,679 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesFrank Wolter (1995). The Finite Model Property in Tense Logic. Journal of Symbolic Logic 60 (3):757-774.
Larisa Maksimova (2002). Complexity of Interpolation and Related Problems in Positive Calculi. Journal of Symbolic Logic 67 (1):397-408.
Alexander Paseau (2010). Pure Second-Order Logic with Second-Order Identity. Notre Dame Journal of Formal Logic 51 (3):351-360.
Ian Hodkinson (2002). Loosely Guarded Fragment of First-Order Logic has the Finite Model Property. Studia Logica 70 (2):205 - 240.
Mitsuhiro Okada & Kazushige Terui (1999). The Finite Model Property for Various Fragments of Intuitionistic Linear Logic. Journal of Symbolic Logic 64 (2):790-802.
Erich Grädel (1999). On the Restraining Power of Guards. Journal of Symbolic Logic 64 (4):1719-1742.
Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi (1997). On the Decision Problem for Two-Variable First-Order Logic. Bulletin of Symbolic Logic 3 (1):53-69.
Savas Konur (forthcoming). An Event-Based Fragment of First-Order Logic Over Intervals. Journal of Logic, Language and Information.
William C. Purdy (1996). Decidability of Fluted Logic with Identity. Notre Dame Journal of Formal Logic 37 (1):84-104.
William C. Purdy (1996). Fluted Formulas and the Limits of Decidability. Journal of Symbolic Logic 61 (2):608-620.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads3 ( #201,930 of 549,088 )Recent downloads (6 months)1 ( #63,317 of 549,088 )How can I increase my downloads? |
My notes
Discussion
