Parametric Interval Temporal Logic over Infinite Words

Laura Bozzelli
(Università di Napoli "Federico II")
Adriano Peron
(Università di Napoli "Federico II")

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.

In Pierre Ganty and Dario Della Monica: Proceedings of the 13th International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2022), Madrid, Spain, September 21-23, 2022, Electronic Proceedings in Theoretical Computer Science 370, pp. 97–113.
Published: 20th September 2022.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: