Inexpressiveness of First-Order Fragments

Australasian Journal of Logic 4 (5):1-12 (2006)
  Copy   BIBTEX

Abstract

It is well-known that first-order logic is semi-decidable. Therefore, first-order logic is less than ideal for computational purposes (computer science, knowledge engineering). Certain fragments of first-order logic are of interest because they are decidable. But decidability is gained at the cost of expressiveness. The objective of this paper is to investigate inexpressiveness of fragments that have received much attention.

Categories

Keywords

Reprint years

DOI

10.26686/ajl.v4i0.1777

Links

PhilArchive



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

External links

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

Through your library

My notes

Similar books and articles

On the Restraining Power of Guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
Temporalising tableaux.Roman Kontchakov, Carsten Lutz, Frank Wolter & Michael Zakharyaschev - 2004 - Studia Logica 76 (1):91 - 134.
Investigations on Fragments of First Order Branching Temporal Logic.Franco Montagna, G. Michele Pinna & B. P. Tiezzi - 2002 - Mathematical Logic Quarterly 48 (1):51-62.
On the restraining power of guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
Decidable fragments of first-order temporal logics.Ian Hodkinson, Frank Wolter & Michael Zakharyaschev - 2000 - Annals of Pure and Applied Logic 106 (1-3):85-134.
First order common knowledge logics.Frank Wolter - 2000 - Studia Logica 65 (2):249-271.
An Event-Based Fragment of First-Order Logic over Intervals.Savas Konur - 2011 - Journal of Logic, Language and Information 20 (1):49-68.
Decidable fragments of first-order modal logics.Frank Wolter & Michael Zakharyaschev - 2001 - Journal of Symbolic Logic 66 (3):1415-1438.
Decidable Fragments of First-Order Modal Logics.Frank Wolter & Michael Zakharyaschev - 2001 - Journal of Symbolic Logic 66 (3):1415-1438.
Interpolation and Definability in Guarded Fragments.Eva Hoogland & Maarten Marx - 2002 - Studia Logica 70 (3):373-409.
Interpolation and definability in guarded fragments.Eva Hoogland & Maarten Marx - 2002 - Studia Logica 70 (3):373 - 409.
Pure Second-Order Logic with Second-Order Identity.Alexander Paseau - 2010 - Notre Dame Journal of Formal Logic 51 (3):351-360.
Counterexamples of the 0-1 law for fragments of existential second-order logic: An overview.Jean-Marie le Bars - 2000 - Bulletin of Symbolic Logic 6 (1):67-82.
First-order Nilpotent minimum logics: first steps.Matteo Bianchi - 2013 - Archive for Mathematical Logic 52 (3-4):295-316.
Some new results on decidability for elementary algebra and geometry.Robert M. Solovay, R. D. Arthan & John Harrison - 2012 - Annals of Pure and Applied Logic 163 (12):1765-1802.

Analytics

Added to PP
2014-03-14

Downloads
12 (#1,025,624)

6 months
1 (#1,459,555)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Syllogistic Logic with Comparative Adjectives.Lawrence S. Moss - 2011 - Journal of Logic, Language and Information 20 (3):397-417.

Add more citations

References found in this work

Distributive Normal Forms in the Calculus of Predicates.Jaakko Hintikka - 1953 - [Edidit Societas Philosophica;,] [Distribuit Akatesminen Kirjakauppa,].
Fluted formulas and the limits of decidability.William C. Purdy - 1996 - Journal of Symbolic Logic 61 (2):608-620.

Add more references