Parameterized linear temporal logics meet costs: still not costlier than LTL

Zimmermann, Martin ORCID: 0000-0002-8038-2453
(2018) Parameterized linear temporal logics meet costs: still not costlier than LTL. ACTA INFORMATICA, 55 (2). pp. 129-152.

[img] Text
costpltl.pdf - Author Accepted Manuscript

Download (747kB) | Preview


We continue the investigation of parameterized extensions of Linear Temporal Logic (LTL) that retain the attractive algorithmic properties of LTL: a polynomial space model checking algorithm and a doubly-exponential time algorithm for solving games. Alur et al. and Kupferman et al. showed that this is the case for Parametric LTL (PLTL) and PROMPT-LTL respectively, which have temporal operators equipped with variables that bound their scope in time. Later, this was also shown to be true for Parametric LDL (PLDL), which extends PLTL to be able to express all omega-regular properties. Here, we generalize PLTL to systems with costs, i.e., we do not bound the scope of operators in time, but bound the scope in terms of the cost accumulated during time. Again, we show that model checking and solving games for specifications in PLTL with costs is not harder than the corresponding problems for LTL. Finally, we discuss PLDL with costs and extensions to multiple cost functions.

Item Type: Article
Additional Information: A short version appears in Proceedings of GandALF 2015
Uncontrolled Keywords: cs.LO, cs.LO, cs.FL
Depositing User: Symplectic Admin
Date Deposited: 15 Jul 2019 12:52
Last Modified: 19 Jan 2023 00:37
DOI: 10.1007/s00236-016-0279-9
Related URLs: