Theories of ω-layered metric temporal structures: expressiveness and decidability

, &
Logic Journal of the IGPL 7 (1):79-102 (1999)
  Copy   BIBTEX

Abstract

This paper focuses on decidability problems for metric and layered temporal logics. The considered logics - suitable to model time granularity in various contexts - allow one to build granular temporal models by referring to the natural scale in any component of the model and properly constraining the interactions between differently grained components. We prove the decidability of both the theory of metric temporal structures provided with an infinite number of arbitrarily coarse temporal layers and the theory of metric temporal structures provided with an infinite number of arbitrarily coarse temporal layers and the theory of metric temporal structures provided with an infinite number of arbitrarily fine temporal layers. The proof for the first theory is obtained by a reduction to the decidability problem of an extension of the standard monadic second-order theory of one successor MSO[<], while the proof for the second one is done through a reduction to the monadic second-order decidable theory of k successors MSO[

Categories

Keywords

Reprint years

DOI

10.1093/jigpal/7.1.79

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 103,703

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

Decidability Results for Metric and Layered Temporal Logics.Angelo Montanari & Alberto Policriti - 1996 - Notre Dame Journal of Formal Logic 37 (2):260-282.
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.
The taming of the states.A. Montanari, A. Peron & A. Policriti - 2000 - Logic Journal of the IGPL 8 (5):681-699.
On the relationships between theories of time granularity and the monadic second-order theory of one successor.Angelo Montanari, Adriano Peron & Gabriele Puppis - 2006 - Journal of Applied Non-Classical Logics 16 (3-4):433-455.
Metric temporal reasoning with less than two clocks.Mark Reynolds - 2010 - Journal of Applied Non-Classical Logics 20 (4):437-455.
A model-theoretic characterization of monadic second order logic on infinite words.Silvio Ghilardi & Samuel J. van Gool - 2017 - Journal of Symbolic Logic 82 (1):62-76.
Decidability and incompleteness results for first-order temporal logics of linear time.Stephan Merz - 1992 - Journal of Applied Non-Classical Logics 2 (2):139-156.
An infinitary variant of Metric Temporal Logic over dense time domains.S. Baratella - 2004 - Mathematical Logic Quarterly 50 (3):249.
A note on unbounded metric temporal logic over dense time domains.Stefano Baratella & Andrea Masini - 2006 - Mathematical Logic Quarterly 52 (5):450-456.
The Unrestricted Combination of Temporal Logic Systems.Marcelo Finger & M. Weiss - 2002 - Logic Journal of the IGPL 10 (2):165-189.

Analytics

Added to PP
2015-02-04

Downloads
5 (#1,785,961)

6 months
1 (#1,598,919)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Add more citations

References found in this work

No references found.

Add more references