Synchronous Signal Temporal Logic for Decidable Verification of Cyber-Physical Systems

Partha Roop, Sobhan Chatterjee, Avinash Malik, Nathan Allen, Logan Kenwright · 2026

Read Synchronous Signal Temporal Logic for Decidable Verification of Cyber-Physical Systems by Partha Roop, Sobhan Chatterjee, Avinash Malik, Nathan Allen, Logan Kenwright (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-25531.txt.

Introduction

Roop and co-authors carve a decidable slice out of Signal Temporal Logic for checking cyber-physical systems. Full static checks of STL are undecidable, so teams fall back on run-time tests. Their SSTL samples signals at fixed ticks and rests on a signal invariance hypothesis. That hypothesis is exactly what makes an STL claim match its SSTL twin. A translation into a predicate form of LTL opens the SPIN checker. A 33-node heart model shows the route works.

Catalog record

CREATORPartha Roop, Sobhan Chatterjee, Avinash Malik, Nathan Allen, Logan Kenwright
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE89348
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.25531

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Synchronous Signal Temporal Logic for Decidable Verification of Cyber-Physical Systems Partha Roop, Sobhan Chatterjee, Avinash Malik, Nathan Allen, Logan Kenwright Abstract . Many Cyber Physical System work in a safety-critical environment, where correct execution, reliability and trustworthiness are essential. Signal Temporal Logic provides a formal framework for checking safety-critical CPS. However, static verification of STL is undecidable,in general, except when we want to verify using run-time-based methods, which have limitations. We propose Synchronous Signal Temporal Logic, a decidable fragment of STL, which admits static safety and liveness property verification. In SSTL, we assume that a signal is sampled at fixed discrete steps, called ticks , and then propose a hypothesis, called the Signal Invariance Hypothesis, which is inspired by a similar hypothesis for synchronous programs. We define the syntax and semantics of SSTL and show that SIH is a necessary and sufficient condition for equivalence between an STL formula and its SSTL counterpart. By translating SSTL to LTL P (LTL defined over predicates), we enable decidable model checking using the SPIN model checker. We demonstrate the approach on a 33-node human heart model and other case studies. 1. Introduction Autonomous systems such as agricultural robots, self-driving vehicles, manufacturing units, amongst others, are a subclass of Cyber Physical System ( Alur 2015 ) , where (usually) discrete and distributed controllers control a continuous plant. Such systems operate within environments with human presence. Hence, guaranteeing their safe operation is essential. Many different techniques for autonomous safety have been proposed. These techniques can be classified into ① static verification ( Althoff et al. 2021 ) , which makes sure that the system is safe for operation before deployment. However, it is well known that static verification of Cyber Physical System is undecidable even in simple cases ( Henzinger et al. 1995 ) . ② Runtime verification of Cyber Physical System ( Dreossi et al. 2019 ; "davidad" Dalrymple et al. 2024 ) , where the verification engine checks the required properties on the deployed system. Runtime verification is complementary to static verification, since it does not enumerate all possible execution paths of the system. ③ Controller synthesis ( Belta and Sadraddini 2019 ) , which produces a controller for a given plant while satisfying the formal properties. The controller synthesis problem, which is formulated as a constrained optimisation problem, has scalability issues for large systems. Irrespective of the chosen option, formal properties of Cyber Physical System are specified in a suitable temporal logic with predicates over continuous variables. Signal Temporal Logic ( Donzé 2013 ) is the most widely used temporal logic for property specification of autonomous CPS. Here, static ( Lercher and Althoff 2024 ) and runtime verification ( Yu et al. 2022 ; Bae and Lee 2019a ) and controller synthesis ( Yang et al. 2020 ; Lindemann and Dimarogonas 2019 ) have been studied. Static verification of Signal Temporal Logic properties is undecidable ( Bae and Lee 2019b ) . Overapproximating the system trajectories can mitigate this problem, to some extent. However, such over-approximation is only applicable for safety properties ( nothing bad ever happens ). To the best of our knowledge, liveness (that something good eventually happens ) properties, expressed in Signal Temporal Logic, have never been statically verified for autonomous systems. We propose to address the challenges of undecidability of Signal Temporal Logic property verification for both safety and liveness in this work. These methods are essential for the verification of environment constraints for safe autonomy to be realisable. We focus on environmental inputs and plant outputs, sensed as time series data, also known as signals . For example, consider a 33-node heart model scenario where we focus on two key nodes in the heart conduction system: the sinoatrial (SA) node and the atrioventricular (AV) node. At any instant in time, the state of the heart can be represented by a vector containing the electrical potentials at these two nodes. Formally, the state vector \vec{x} is a map, \vec{x}:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}^{2} , where the domain captures any instant in time and the range gives the pair of potentials at the SA and AV nodes at that time. Here, the progression of time is continuous, whose domain is \mathbb{R}_{\geq 0} , also known as real-time systems . Verification of signals in the real-time setting is undecidable. Here, we consider an alternative, also known as the discrete time setting, where time progresses in discrete steps, whose domain is \mathbb{N}_{\geq 0} . This approach is used in many practical systems, including all systems which are realised on a discrete computer, say by sampling some input. A programming paradigm, called synchronous programming ( Benveniste et al. 2003 ) , is based on such environmental sampling using discrete instants called ticks . The rationale for using the synchronous formulation for discritising Signal Temporal Logic is as follows: (1) Any signal from a physical source has inertia proportional to its mass. For example, the ECG sensor. Here, after a P , which means an atrial depolarisation (beat), there is a gap before the next event Q , which indicates the start of the ventricular depolarisation. (2) In signal processing, in addition to transforms over continuous signals, there are transforms over the discrete versions. Consider the Fourier transform (FT) and the discrete Fourier transform (DFT). While FT is suitable for a theoretical analysis over the continuous time signal, DFT is suitable for the design of computational algorithms over sampled signals. Hence, we argue that a synchronous variant of Signal Temporal Logic is needed, where we discretise the logic itself. (3) In synchronous programming ( Benveniste et al. 2003 ) , which is widely used for Cyber Physical System, a hypothesis is used to constrain the environment. This is known as the synchrony hypothesis , which states that the control system reacts infinitely fast relative to its plant . In other words, it requires that data from sensors does not arrive faster than the rate at which the controller can process the data. This hypothesis can be adapted in our setting to formalise the relationship between Signal Temporal Logic and its abstraction, which we term Synchronous Signal Temporal Logic , especially to formalise the status of a signal between two sample points. Based on the above, our premise is that a discrete variant of Signal Temporal Logic, which discretises the Signal Temporal Logic logic and is developed for synchronous systems, called Synchronous Signal Temporal Logic, will lead to methods for scalable verification of Cyber Physical System. We also argue that, under suitable assumptions of robustness ( Fainekos and Pappas 2009 ) , Synchronous Signal Temporal Logic is a sound and complete abstraction of Signal Temporal Logic. The main contributions of the paper are as follows: (1) We propose the first synchronous (discrete) abstraction of the Signal Temporal Logic logic, called Synchronous Signal Temporal Logic. We introduce a decidable encoding of Signal Temporal Logic (STL) called Synchronous Signal Temporal Logic (SSTL). (2) We define the syntax and semantics of Synchronous Signal Temporal Logic and prove that under a suitable assumption of signal characteristics, this can be used as a sound and complete abstraction of Signal Temporal Logic. (3) We present an LTL P translation of Synchronous Signal Temporal

Read the complete text