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||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Frank Wolter (1995). The Finite Model Property in Tense Logic. Journal of Symbolic Logic 60 (3):757-774.
William C. Purdy (1996). Decidability of Fluted Logic with Identity. Notre Dame Journal of Formal Logic 37 (1):84-104.
Savas Konur (2011). An Event-Based Fragment of First-Order Logic Over Intervals. Journal of Logic, Language and Information 20 (1):49-68.
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.
Erich Grädel (1999). On the Restraining Power of Guards. Journal of Symbolic Logic 64 (4):1719-1742.
Mitsuhiro Okada & Kazushige Terui (1999). The Finite Model Property for Various Fragments of Intuitionistic Linear Logic. Journal of Symbolic Logic 64 (2):790-802.
Ian Hodkinson (2002). Loosely Guarded Fragment of First-Order Logic has the Finite Model Property. Studia Logica 70 (2):205 - 240.
Alexander Paseau (2010). Pure Second-Order Logic with Second-Order Identity. Notre Dame Journal of Formal Logic 51 (3):351-360.
Larisa Maksimova (2002). Complexity of Interpolation and Related Problems in Positive Calculi. Journal of Symbolic Logic 67 (1):397-408.
William C. Purdy (1996). Fluted Formulas and the Limits of Decidability. Journal of Symbolic Logic 61 (2):608-620.
Added to index2009-01-28
Total downloads4 ( #188,845 of 722,775 )
Recent downloads (6 months)1 ( #60,541 of 722,775 )
How can I increase my downloads?