Path Checking for MTL and TPTL over Data Words

摘要

Metric temporal logic (MTL) and timed propositional temporal logic (TPTL) arequantitative extensions of linear temporal logic, which are prominent andwidely used in the verification of real-timed systems. It was recently shownthat the path checking problem for MTL, when evaluated over finite timed words,is in the parallel complexity class NC. In this paper, we derive precisecomplexity results for the path-checking problem for MTL and TPTL whenevaluated over infinite data words over the non-negative integers. Such wordsmay be seen as the behaviours of one-counter machines. For this setting, wegive a complete analysis of the complexity of the path-checking problemdepending on the number of register variables and the encoding of constraintnumbers (unary or binary). As the two main results, we prove that thepath-checking problem for MTL is P-complete, whereas the path-checking problemfor TPTL is PSPACE-complete. The results yield the precise complexity of modelchecking deterministic one-counter machines against formulae of MTL and TPTL.