It is known that the satisfiability problem for Metric Temporal Logic (MTL) is decidable over finite timed words. In this paper we study the satisfiability problem for extensions of this logic by various process-algebraic operators. On the negative side we show that satisfiability becomes undecidable when any of hiding, renaming, or asynchronous parallel composition are added to the logic. On the positive side we show decidability with the addition of alphabetised parallel composition and fixpoint operators. We use one-clock Timed Propositional Temporal Logic (TPTL(1)) as a technical tool for the decidability results and show that TPTL(1) with fixpoints provides a logical characterisation of the class of languages accepted by one-clock timed alternating automata.
Reflections on the Work of C.A.R. Hoare, 2010. 18 pages.
PDF
© 2010
Springer-Verlag.