Parametric Interval Temporal Logic over Infinite Words

Abstract

Model checking for Halpern and Shoham's interval temporal logic HS has been recently investigated in a systematic way, and it is known to be decidable under three distinct semantics. Here, we focus on the trace-based semantics, where the infinite execution paths (traces) of the given (finite) Kripke structure are the main semantic entities. In this setting, each finite infix of a trace is interpreted as an interval, and a proposition holds over an interval if and only if it holds over each component state (homogeneity assumption). In this paper, we introduce a quantitative extension of HS over traces, called parametric HS (PHS). The novel logic allows to express parametric timing constraints on the duration (length) of the intervals. We show that checking the existence of a parameter valuation for which a Kripke structure satisfies a PHS formula (model checking), or a PHS formula admits a trace as a model under the homogeneity assumption (satisfiability) is decidable. Moreover, we identify a fragment of PHS which subsumes parametric LTL and for which model checking and satisfiability are shown to be EXPSPACE-complete.

arXiv commentIn Proceedings GandALF 2022, arXiv:2209.09333

References in corpus (5)

• Checking Interval Properties of Computations
• A decidable weakening of Compass Logic based on cone-shaped cardinal directions
• Interval vs. Point Temporal Logic Model Checking: an Expressiveness Comparison
• Satisfiability and Model Checking for the Logic of Sub-Intervals under the Homogeneity Assumption
• Adding the Relation Meets to the Temporal Logic of Prefixes and Infixes makes it EXPSPACE-Complete