Decidability results for metric and layered temporal logics

DOI10.1305/NDJFL/1040046089MaRDI QIDQ1815429zbMATH OpenOpenAlexFDO

Authors Angelo Montanari, Alberto Policriti

Publication date 19 March 1997

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/f31ed54db3d65d509276d20c019179c047dd0902

zbMATH Keywords

decidabilitymetric and layered temporal logicstime granularity

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Modal logic (including the logic of norms) (03B45)

Review text

The decidability problem for metric and layered temporal logics (MLTL for short) is studied. Metric temporal logics extend propositional logic with a parametrized operator of relative temporal realization. MLTL can be viewed as the combination of a number of differently grained metric temporal logics. It replaces the flat temporal domain of metric temporal logics with a temporal universe consisting of a set of differently grained temporal domains together with relations between instants belonging to different domains. The decidability of MLTL is studied by embedding finitely layered metric temporal structures into their finest metric component, and then reducing the decidability of the theory of the simplest component to a theory that is known to be decidable, namely S1S (the second-order theory of one successor).

Recommendations

• Publication:4952306
• Theories of  -layered metric temporal structures: expressiveness and decidability
• Decidable metric logics
• Tools and Algorithms for the Construction and Analysis of Systems
• On the decidability and complexity of Metric Temporal Logic over finite words

Cites work

• A set-theoretic translation method for polymodal logics
• Combining temporal logic systems
• Embedding time granularity in a logical specification language for synchronous real-time systems
• Handbook of mathematical logic. With the cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis, A. S. Troelstra. 2nd printing
• scientific article; zbMATH DE number 52331 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 1536547 (Why is no real title available?)
• scientific article; zbMATH DE number 1444726 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• scientific article; zbMATH DE number 3316928 (Why is no real title available?)
• Real-time logics: Complexity and expressiveness
• Specifying message passing and time-critical systems with temporal logic
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(12)

• Timer formulas and decidable metric temporal logic
• A two-level temporal logic for evolving specifications.
• Definability and decidability of binary predicates for time granularity
• On the relationships between theories of time granularity and the monadic second-order theory of one successor
• Theories of  -layered metric temporal structures: expressiveness and decidability
• scientific article; zbMATH DE number 1405657 (Why is no real title available?)
• scientific article; zbMATH DE number 1444726 (Why is no real title available?)
• On Metric Temporal Łukasiewicz Logic
• On the decidability and complexity of Metric Temporal Logic over finite words
• Tools and Algorithms for the Construction and Analysis of Systems
• Decidability of logics based on an indeterministic metric tense logic
• Decidable metric logics

This page was built for publication: Decidability results for metric and layered temporal logics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1815429)