Axiomatizing the monodic fragment of first-order temporal logic

&
Annals of Pure and Applied Logic 118 (1-2):133-145 (2002)
  Copy   BIBTEX

Abstract

It is known that even seemingly small fragments of the first-order temporal logic over the natural numbers are not recursively enumerable. In this paper we show that the monodic fragment is an exception by constructing its finite Hilbert-style axiomatization. We also show that the monodic fragment with equality is not recursively axiomatizable

Categories

Keywords

Reprint years

DOI

10.1016/s0168-0072(01)00124-5

Links

PhilArchive



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

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

Temporalising tableaux.Roman Kontchakov, Carsten Lutz, Frank Wolter & Michael Zakharyaschev - 2004 - Studia Logica 76 (1):91 - 134.
Equality and monodic first-order temporal logic.Anatoli Degtyarev, Michael Fisher & Alexei Lisitsa - 2002 - Studia Logica 72 (2):147-156.
Monodic packed fragment with equality is decidable.Ian Hodkinson - 2002 - Studia Logica 72 (2):185-197.
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 temporal logics.Ian Hodkinson, Frank Wolter & Michael Zakharyaschev - 2000 - Annals of Pure and Applied Logic 106 (1-3):85-134.
Deciding regular grammar logics with converse through first-order logic.Stéphane Demri & Hans De Nivelle - 2005 - Journal of Logic, Language and Information 14 (3):289-329.
Adding a temporal dimension to a logic system.Marcelo Finger & Dov M. Gabbay - 1992 - Journal of Logic, Language and Information 1 (3):203-233.
The undecidability of second order linear logic without exponentials.Yves Lafont - 1996 - Journal of Symbolic Logic 61 (2):541-548.
Axiomatizing the next-interior fragment of dynamic topological logic.Philip Kremer, Grigori Mints & V. Rybakov - 1997 - Bulletin of Symbolic Logic 3:376-377.
Undecidability of first-order intuitionistic and modal logics with two variables.Roman Kontchakov, Agi Kurucz & Michael Zakharyaschev - 2005 - Bulletin of Symbolic Logic 11 (3):428-438.
Expressive completeness of temporal logic of trees.Bernd-Holger Schlingloff - 1992 - Journal of Applied Non-Classical Logics 2 (2):157-180.
Expressivity of second order propositional modal logic.Balder ten Cate - 2006 - Journal of Philosophical Logic 35 (2):209-223.
Loosely guarded fragment of first-order logic has the finite model property.Ian Hodkinson - 2002 - Studia Logica 70 (2):205 - 240.
A phase semantics for polarized linear logic and second order conservativity.Masahiro Hamano & Ryo Takemura - 2010 - Journal of Symbolic Logic 75 (1):77-102.

Analytics

Added to PP
2014-01-16

Downloads
26 (#610,794)

6 months
19 (#135,597)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Temporal logic.Antony Galton - 2008 - Stanford Encyclopedia of Philosophy.

View all 11 citations / Add more citations

References found in this work

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.
Fluted formulas and the limits of decidability.William C. Purdy - 1996 - Journal of Symbolic Logic 61 (2):608-620.
Decidability of Fluted Logic with Identity.William C. Purdy - 1996 - Notre Dame Journal of Formal Logic 37 (1):84-104.

Add more references