MTL and TPTL for One-Counter Machines: Expressiveness, Model Checking, and Satisfiability

摘要

Metric Temporal Logic (MTL) and Timed Propositional Temporal Logic (TPTL) are quantitative extensions of Linear Temporal Logic (LTL) that are prominent and widely used in the verification of real-timed systems. We study MTL and TPTL as specification languages for one-counter machines. It is known that model checking one-counter machines against formulas of Freeze LTL (FLTL), a strict fragment of TPTL, is undecidable. We prove that in our setting, MTL is strictly less expressive than TPTL, and incomparable in expressiveness to FLTL, so undecidability for MTL is not implied by the result for FLTL. We show, however, that the model-checking problem for MTL is undecidable. We further prove that the satisfiability problem for the unary fragments of TPTL and MTL are undecidable; for TPTL, this even holds for the fragment in which only one register and the finally modality is used. This is opposed to a known decidability result for the satisfiability problem for the same fragment of FLTL.