Oxford Journals
tools journals homepage advanced search contact help
Journal of Logic and Computation: Current Issue
 
home
browse
current
etoc
authors
subinfo
subscribers
samples

OUP > Journals > Computing/Engineer. & Mathematics/Stats. > Journal of Logic and Computation

Journal of Logic and Computation

Volume 12, Issue 2, April 2002: pp. 243-253

Monadic Logic of Order over Naturals has no Finite Base

Danièle Beauquier1 and Alexander Rabinovich2

1Laboratory of Algorithmics, Complexity and Logic, Department of Informatics, University Paris-12, France. E-mail: beauquier@univ-paris12.fr
2Department of Computer Science, Tel-Aviv University, Israel. E-mail: rabino@math.tau.ac.il

A major result concerning Temporal Logics (T L) is Kamp's theorem which states that the temporal logic over the pair of modalities X until Y and X since Y is expressively complete for the first-order fragment of monadic logic of order over the natural numbers. We show that there is no finite set of modalities B such that the temporal logic over B and monadic logic of order have the same expressive power over the natural numbers. As a consequence of our proof, we obtain that there is no finite base temporal logic which is expressively complete for the [mgr]-calculus.

Keywords: Temporal logics; monadic logics

Table of Contents   Full-Text PDF (150 KB)

Oxford University Press
Published by Oxford University Press
Copyright ©Oxford University Press 2003
Print ISSN: 0955-792X  Online ISSN: 1465-363X.
Oxford University Press Privacy Policy and Legal Statement