2026-07-21T23:46:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11595 2024-03-06T10:48:24Z ddc:004 open_access

Interval Temporal Logic for Visibly Pushdown Systems Bozzelli, Laura Montanari, Angelo Peron, Adriano Pushdown systems Interval temporal logic Model checking In this paper, we introduce and investigate an extension of Halpern and Shoham’s interval temporal logic HS for the specification and verification of branching-time context-free requirements of pushdown systems under a state-based semantics over Kripke structures. Both homogeneity and visibility are assumed. The proposed logic, called nested BHS, supports branching-time both in the past and in the future, and is able to express non-regular properties of linear and branching behaviours of procedural contexts in a natural way. It strictly subsumes well-known linear time context-free extensions of LTL such as CaRet [R. Alur et al., 2004] and NWTL [R. Alur et al., 2007]. The main result is the decidability of the visibly pushdown model-checking problem against nested BHS. The proof exploits a non-trivial automata-theoretic construction. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Laura Bozzelli and Angelo Montanari and Adriano Peron 2019 Is Part Of LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2019.33 urn:nbn:de:0030-drops-115959 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.33 eng https://creativecommons.org/licenses/by/3.0/legalcode