𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Decidable fragments of first-order temporal logics

✍ Scribed by Ian Hodkinson; Frank Wolter; Michael Zakharyaschev

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
342 KB
Volume
106
Category
Article
ISSN
0168-0072

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we introduce a new fragment of the ÿrst-order temporal language, called the monodic fragment, in which all formulas beginning with a temporal operator (Since or Until) have at most one free variable. We show that the satisÿability problem for monodic formulas in various linear time structures can be reduced to the satisÿability problem for a certain fragment of classical ÿrst-order logic. This reduction is then used to single out a number of decidable fragments of ÿrst-order temporal logics and of two-sorted ÿrst-order logics in which one sort is intended for temporal reasoning. Besides standard ÿrst-order time structures, we consider also those that have only ÿnite ÿrst-order domains, and extend the results mentioned above to temporal logics of ÿnite domains. We prove decidability in three di erent ways: using decidability of monadic second-order logic over the intended ows of time, by an explicit analysis of structures with natural numbers time, and by a composition method that builds a model from pieces in ÿnitely many steps.

📜 SIMILAR VOLUMES

Axiomatizing the monodic fragment of fir
Axiomatizing the monodic fragment of first-order temporal logic
✍ Frank Wolter; Michael Zakharyaschev 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 141 KB

It is known that even seemingly small fragments of the ÿrst-order temporal logic over the natural numbers are not recursively enumerable. In this paper we show that the monodic (not monadic, where this result does not hold) fragment is an exception by constructing its ÿnite Hilbert-style axiomatizat

Decidability and Definability Results Co
Decidability and Definability Results Concerning Well-Orderings and Some Extensions of First Order Logic
✍ Bogdan Stanislaw Chlebus 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 452 KB

DECIDABILITY AND DEFINABILITY RESULTS CONCERNING WELL-ORDERINGS AND SOME EXTENSIONS OF FIRST ORDER LOGIC by BOGDAN STANISLAW CHLEBUS in Warsaw (Poland) ## 1. Introdiirtion Let L\* denote a countable extension of the first order language L. I n this paper 1 ) definability of the class of well-order