Complexity and Nicety of Fluted Logic

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


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.



    Upload a copy of this work     Papers currently archived: 91,122

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Complexity and nicety of fluted logic.William C. Purdy - 2002 - Studia Logica 71 (2):177 - 198.
Decidability of Fluted Logic with Identity.William C. Purdy - 1996 - Notre Dame Journal of Formal Logic 37 (1):84-104.
Book Reviews. [REVIEW]Jacek Paśniczek - 2000 - Studia Logica 65 (3):429-446.
Fuzzy logic and arithmetical hierarchy III.Petr Hájek - 2001 - Studia Logica 68 (1):129-142.


Added to PP

8 (#1,215,626)

6 months
1 (#1,346,405)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

More Fragments of Language.Ian Pratt-Hartmann & Allan Third - 2006 - Notre Dame Journal of Formal Logic 47 (2):151-177.
The fluted fragment with transitive relations.Ian Pratt-Hartmann & Lidia Tendera - 2022 - Annals of Pure and Applied Logic 173 (1):103042.

Add more citations

References found in this work

No references found.

Add more references