Synchronous Signal Temporal Logic for Decidable Verification of Cyber-Physical Systems
Many Cyber Physical System (CPS) work in a safety-critical environment, where correct execution, reliability and trustworthiness are essential. Signal Temporal Logic (STL) 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 (SSTL), 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, calle — Partha Roop, Sobhan Chatterjee, Avinash Malik
View PDF HTML (experimental)
Abstract:Many Cyber Physical System (CPS) work in a safety-critical environment, where correct execution, reliability and trustworthiness are essential. Signal Temporal Logic (STL) 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 (SSTL), 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 (SIH), 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.
Subjects:
Formal Languages and Automata Theory (cs.FL); Computation and Language (cs.CL)
Cite as: arXiv:2603.25531 [cs.FL]
(or arXiv:2603.25531v1 [cs.FL] for this version)
https://doi.org/10.48550/arXiv.2603.25531
arXiv-issued DOI via DataCite (pending registration)
Submission history
From: Logan Kenwright [view email] [v1] Thu, 26 Mar 2026 15:06:17 UTC (177 KB)
Sign in to highlight and annotate this article
Conversation starters
Daily AI Digest
Get the top 5 AI stories delivered to your inbox every morning.
More about
researchpaperarxiv
Consistency Amplifies: How Behavioral Variance Shapes Agent Accuracy
Analysis of behavioral consistency in large language model agents reveals that while consistent performance correlates with higher accuracy, consistency can amplify both correct and incorrect interpretations, emphasizing that accurate interpretation is more crucial than execution consistency for production deployment. (2 upvotes on HuggingFace)
Brevity Constraints Reverse Performance Hierarchies in Language Models
Large language models can underperform smaller ones due to verbose responses that introduce errors, but constraining output length reveals their superior capabilities and improves performance across benchmarks. (16 upvotes on HuggingFace)
Knowledge Map
Connected Articles — Knowledge Graph
This article is connected to other articles through shared AI topics and tags.
More in Research Papers
Consistency Amplifies: How Behavioral Variance Shapes Agent Accuracy
Analysis of behavioral consistency in large language model agents reveals that while consistent performance correlates with higher accuracy, consistency can amplify both correct and incorrect interpretations, emphasizing that accurate interpretation is more crucial than execution consistency for production deployment. (2 upvotes on HuggingFace)
Brevity Constraints Reverse Performance Hierarchies in Language Models
Large language models can underperform smaller ones due to verbose responses that introduce errors, but constraining output length reveals their superior capabilities and improves performance across benchmarks. (16 upvotes on HuggingFace)
Reasoning Shift: How Context Silently Shortens LLM Reasoning
Reasoning behaviors in large language models compress under varied contextual conditions, potentially impacting performance on complex tasks despite maintaining accuracy on simpler ones. (22 upvotes on HuggingFace)
Discussion
Sign in to join the discussion
No comments yet — be the first to share your thoughts!