Expressive completeness of temporal logic of trees

Journal of Applied Non-Classical Logics 2 (2):157-180 (1992)
  Copy   BIBTEX


ABSTRACT Many temporal and modal logic languages can be regarded as subsets of first order logic, i.e. the semantics of a temporal logic formula is given as a first order condition on points of the underlying models (Kripke structures). Often the set of possible models is restricted to models which are trees. A temporal logic language is (first order) expressively complete, if for every first order condition for a node of a tree there exists an equivalent temporal formula which expresses the same condition. In this paper expressive completeness of the temporal logic language with the set of operators U (until), S (since), and X k (k-next) is proved, and the result is extended to various other tree-like structures



    Upload a copy of this work     Papers currently archived: 74,569

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

Naming Worlds in Modal and Temporal Logic.D. M. Gabbay & G. Malod - 2002 - Journal of Logic, Language and Information 11 (1):29-65.
Adding a Temporal Dimension to a Logic System.Marcelo Finger & Dov M. Gabbay - 1992 - Journal of Logic, Language and Information 1 (3):203-233.
Hierarchies of Modal and Temporal Logics with Reference Pointers.Valentin Goranko - 1996 - Journal of Logic, Language and Information 5 (1):1-24.
Bisimulations for Temporal Logic.Natasha Kurtonina & Maarten de Rijke - 1997 - Journal of Logic, Language and Information 6 (4):403-425.
An Extended Branching-Time Ockhamist Temporal Logic.Mark Brown & Valentin Goranko - 1999 - Journal of Logic, Language and Information 8 (2):143-166.
Querying Linguistic Trees.Catherine Lai & Steven Bird - 2010 - Journal of Logic, Language and Information 19 (1):53-73.
Propositional Q-Logic.Stefan Wölfl - 2002 - Journal of Philosophical Logic 31 (5):387-414.
An Event-Based Fragment of First-Order Logic Over Intervals.Savas Konur - 2011 - Journal of Logic, Language and Information 20 (1):49-68.
Decidability of an Xstit Logic.Gillman Payette - 2014 - Studia Logica 102 (3):577-607.


Added to PP

37 (#313,158)

6 months
3 (#210,812)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Finite H-Dimension Does Not Imply Expressive Completeness.Ian Hodkinson - 1994 - Journal of Philosophical Logic 23 (5):535 - 573.

Add more citations

References found in this work

Tense Logic and the Theory of Linear Order.Johan Anthony Wilem Kamp - 1968 - Dissertation, University of California, Los Angeles

Add more references