Decidable metric logics

• Published in: Information and computation 2008-12, Vol.206 (12), p.1425-1442
• Main Authors: Hirshfeld, Yoram, Rabinovich, Alex
• Format: Article
• Language: English
• Subjects: Applied sciences; Computer science; control theory; systems; Exact sciences and technology; General logic; Logic and foundations; Mathematical logic, foundations, set theory; Mathematics; Miscellaneous; Sciences and techniques of general use; Theoretical computing
• ISSN: 0890-5401; 1090-2651
• DOI: 10.1016/j.ic.2008.08.004

The common metric temporal logic for continuous time were shown to be insufficient, when it was proved that they cannot express a modality suggested by Pnueli. Moreover no finite temporal logic can express all the natural generalizations of this modality. It followed that if we look for an optimal decidable metric logic we must accept infinitely many modalities, or adopt a different formalism. Here we identify a fragment of the second order monadic logic of order with the “ + 1 ” function, that expresses all the Pnueli modalities and much more. Its main advantage over the temporal logics is that it enables us to say not just that within prescribed time there is a point where some punctual event will occur, but also that within prescribed time some process that starts now (or that started before, or that will start soon) will terminate. We prove that this logic is decidable with respect to satisfiability and validity, over continuous time. The proof depends heavily on the theory of compositionality. In particular every temporal logic that has truth tables in this logic is automatically decidable. We extend this result by proving that any temporal logic, that has all its modalities defined by means more general than truth tables, in a logic stronger than the one just described, has a decidable satisfiability problem. We suggest that this monadic logic can be the framework in which temporal logics can be safely defined, with the guarantee that their satisfiability problem is decidable.