CS Paper Radar

Compositional Approximately Bisimilar Abstractions of Stochastic Interconnected Systems

S. Saharsh, B. A. Sadek, Abdalla Swikir, Pushpak Jagtap, Adnane Saoud

eess.SY ·submitted 2026-10-26 06:16 UTC · v1

Abstract

This paper addresses the challenge of constructing (alternating) bisimilar symbolic models for discrete-time, stochastic, interconnected systems. By leveraging a refined over-approximation of the stochastic reachable sets and the q-th moment input-to-state stability (delta-ISS-Mq) property, we establish an approximate bisimulation relation between stochastic systems and their deterministic (noise-free) counterparts. This approach significantly simplifies the analysis of the approximate (alternating) bisimulation between the global interconnected stochastic system and its symbolic model. We derive formal conditions under which local bisimulation relations are preserved when composing subsystems into a global interconnected system. The engineering relevance of the proposed compositional framework is demonstrated through temperature regulation case studies involving a fixed ten-room building and a circular cascade interconnection scaled from six to fourteen rooms. The results show that, beyond a small number of subsystems, the proposed method achieves substantially faster abstraction computation times than standard monolithic approaches, with the performance gap widening as the number of interconnected subsystems grows and the monolithic approach failing to converge beyond ten rooms.

Comment
31 pages, 7 Figures

Closest papers

Nearest neighbours by meaning across the whole index.

A Pragmatic Guide to Building Conservative Discrete Abstractions of Cyber-Physical Systems

eess.SY cs.LO ·2026-08-10 ·Jordan Peper, Krish Kapadia, James Gast, Ethan Howes, Ivan Ruchkin
similarity 0.56
Abstract

Symbolic model checking is an effective approach for verifying semantically rich temporal-logic properties of cyber-physical systems, but it hinges on discretizing continuous-state dynamics into a finite-state abstraction. To transfer verification guarantees from the abstract model to the concrete CPS, the abstraction must conservatively approximate the concrete state space and behaviors. Hence, model-builders must maintain this soundness while balancing pessimism with tractability. However, they face several common pitfalls such as under-approximating the state space, under-approximating transitions, unsound pruning of "degenerate" behaviors, and improper specification lifting. This tutorial presents a pragmatic, conservative-by-construction workflow for building discrete abstractions of closed-loop dynamical systems. The workflow consists of four modular steps with interchangeable subroutines: (i) state-space partition and abstraction-function design, (ii) conservative transition construction via axis-aligned bounding boxes, polytopes, or sampling with PAC coverage certificates, (iii) mitigation of spurious transitions and self-loops using certified erasure and counterexample-guided abstraction refinement, and (iv) sound lifting of LTL specifications using may-must semantics. We demonstrate the end-to-end pipeline on three case studies and report how these design choices affect abstraction structure, runtime, and verification outcomes.

0.04

Compositional Sensitivity Analysis for Multiobjective System Co-Design

eess.SY math.OC ·2026-10-13 ·Alan Bonomi, Antonio Terpin, Yubo Cai, Yujun Huang, Meshal Alharbi +1 more
similarity 0.56
Abstract

Sensitivity analysis of coupled systems typically propagates derivatives of single-valued maps, whereas multiobjective optimization generally treats sensitivity at the system level rather than through interconnected subsystems. We develop a mathematical framework for compositional sensitivity analysis in multiobjective system design, building on monotone co-design. Subsystems are represented as design problems (DPs), interconnected through series, parallel, union, intersection, and feedback composition. We introduce tangential DPs (TDPs) to describe first-order variations around an operating point, show that they preserve the structure of DPs, and characterize their queries through graphical derivatives. To account for multiple internal realizations of a system-level operating point, tangential co-design problems compose families of local TDPs by taking a union over these realizations while retaining the original interconnection structure. We show that these compositions yield families of TDPs and establish conditions under which sensitivity analysis commutes with individual composition operations. Beyond infinitesimal sensitivity, we show that bounded tangential models of convex DPs provide tighter outer approximations of feasible finite changes, which can be propagated through co-design problems without union compositions. We conclude with several convex and nonconvex numerical examples that showcase the framework's accuracy and computational benefits.

0.42

A Lumpability-Driven Taxonomy of Strong and Weak Stochastic Bisimilarities with Their Congruence Properties

cs.LO ·2026-09-10 ·Riccardo Romanello, Andrea Esposito, Marco Bernardo, Carla Piazza, Sabina Rossi
similarity 0.56
Abstract

We study the relationships among the stochastic bisimulation-style equivalences over PEPA - Performance Evaluation Process Algebra definable according to the well known notions of lumpability for the continuous-time Markov chains (CTMCs) underlying process terms. Lumpability is a central tool in the analysis of a CTMC, because it results in aggregations of the state space enjoying properties that are useful for efficiently computing the state probability distribution of the original chain. At the level of process terms, various stochastic bisimilarities accounting for activity types and cumulative rates can be defined over PEPA, which induce different kinds of lumping. Since the formalisations of some of them are scattered across the literature, where they appear under different, and sometimes clashing, names, we collect them within a single, uniform framework, renaming each bisimilarity in a consistent way after the kind of lumping it induces. We present strong and weak variants of what we call ordinary, exact, and strict bisimilarities and show that they respectively induce ordinary, exact, and strict lumpings. We then organise the six bisimilarities into a taxonomy establishing all and only the inclusions holding among them. We also analyse how the taxonomy changes in three special cases: process terms whose underlying CTMCs are time reversible, process terms with no activities of unobservable types, and process terms with no recursion. The paper concludes by investigating the compositionality properties of the six bisimilarities. Some of them are not congruences with respect to the prefix and/or choice operators of PEPA. In that case we single out either a set of process terms over which congruence with respect to those operators is achieved, or the coarsest congruence with respect to them that is contained in the considered bisimilarity.

0.33

Memory-Dependent Interval Markov Chain Abstractions of Stochastic Dynamics

eess.SY math.DSmath.OC ·2026-10-02 ·Menno van Zutphen, Adrien Banse, Domagoj Herceg, Giannis Delimpaltadakis, Duarte Antunes
theory similarity 0.52
Abstract

Finite-state interval Markov-chain (IMC) abstractions provide sound verification and performance bounds for continuous-state stochastic systems by enclosing cell-to-cell transition probabilities and costs in intervals. Finite-state Markovian abstractions are generally lossy, as state aggregation often destroys the Markov property. Recently, memory-dependent Markov-chain (MC) abstractions of stochastic systems have been developed to mitigate this by recording recently visited cells. In this paper, we develop the memory-dependent extension of IMC abstractions. Building on the insight that memory narrows the family of state distributions that could occur inside the current cell, we prove that memory tightens the local intervals, at the price of a larger abstraction. We also formulate no-memory IMC abstractions, tightening classic IMC abstraction intervals without enlarging the state space. To characterize spatial refinement relative to memory, we derive two cost-guarantee tightness upper bounds. The bounds depend, respectively, on cell size, and on the worst-case remaining distributional ambiguity after filtering over the remembered past. We then specialize our result to linear-Gaussian systems, for which we derive a closed-form upper bound on this ambiguity. Numerical examples show that the memory-dependent and no-memory constructions can produce tighter expected-cost intervals than comparable partition refined models.

0.22

Perturbation equivalence in labelled Markov chains

cs.LO cs.FL ·2026-09-11 ·Syyeda Zainab Fatmi, Stefan Kiefer, James C. A. Main, David Parker
theory similarity 0.49
Abstract

Behavioural equivalences, such as language equivalence and probabilistic bisimilarity, are fundamental techniques for reducing the size of probabilistic models. However, these equivalences are sensitive to the precise values of transition probabilities, making them unsuitable in applications where probabilities are subject to approximation. Motivated by settings in which the support graph of a labelled Markov chain is known but the transition probabilities are uncertain, we study robust variants of these equivalences. We introduce universal (perturbation) equivalence, which captures a variant of equivalence that is resilient to all perturbations of transition probabilities: two states or distributions are universally equivalent if they remain equivalent under every assignment of transition probabilities consistent with the support graph. We also consider the dual notion of existential (perturbation) equivalence, which holds whenever there exists an assignment of transition probabilities that yields equivalence. We establish that, for states, universal language equivalence coincides with universal probabilistic bisimilarity and develop a characterisation that yields a polynomial-time partition refinement algorithm. We implement the algorithm and demonstrate experimentally that it is effective as a technique for robust model reduction. We further show that universal language equivalence for distributions is closely related to the state case, and prove NL-completeness of deciding universal equivalence for both states and distributions. We prove that, for states, existential language equivalence coincides with existential probabilistic bisimilarity and deterministic witness transition functions always suffice, leading to an NP-completeness result. In contrast, we show that existential language equivalence for distributions is complete for the existential theory of the reals.

0.32

On the Multi-Index, Multi-Rate, and Multi-Phase Dynamics of Decoder-Only Language Models: A Unified Hybrid Framework for Generative and Agentic Systems

eess.SY math.OC ·2026-10-01 ·Ali Pakniyat
similarity 0.49
Abstract

Large language models (LLMs) are increasingly deployed as computational engines in autonomous decision-making and planning loops, yet their systems and control treatment remains hindered by architectural simplifications, index conflations, and informal descriptions of tool interactions. This paper presents a control-theoretic formulation of decoder-only language models as multi-index, multi-rate systems, and sets the stage for a stochastic hybrid systems framework to govern the multi-phase dynamics of agentic tool interaction. We formalize the architecture across three hierarchically coupled evolution indices: (i) an ultrafast feedforward cascade of transformer blocks across layer depth, where layer normalization is cast as a spherical projection and key--value caching is proven to be an exact internal state realization via causal prefix invariance; (ii) an uncontrolled stochastic difference recursion over token generation steps, where finite context truncation induces a time-homogeneous Markov chain; and (iii) an autonomous mode-switching mechanism governing transitions between token generation and tool execution regimes, where tool invocations are triggered upon trajectory arrival at switching manifolds, followed by exogenous state jump maps that augment the context string with external observations. By defining a prompt-dependent evaluator over successive evaluable claims, we obtain a task-level error process whose fault-free histories and expected error growth admit bounds under conditional fault-hazard and error-drift assumptions.

0.25

Data-Driven Compositional Safety Verification of Interconnected Monotone Systems

eess.SY ·2026-09-16 ·Amirreza Alavi, Majid Zamani, Saber Jafarpour
similarity 0.48
Abstract

This paper introduces a sample-efficient compositional method for formal safety verification of interconnected monotone systems without requiring explicit models of the local subsystems. Existing data-driven approaches either lack formal safety guarantees or rely on dense Lipschitz-based discretizations of the state space to provide such guarantees, which leads to significant computational overhead and limits scalability. In contrast, we leverage the monotonicity of local subsystems to construct tractable local interval-barrier certificates using only boundary evaluations of each subsystem in a decentralized manner, together with a global condition that guarantees the safety of the overall interconnected system. At the local level, our framework learns interval-barrier certificates using monotone neural networks from boundary samples induced by partitions of the local state and internal-input spaces. At the global level, it composes these local neural interval-barrier certificates using the interconnection structure to certify the safety of the overall system. Furthermore, under appropriate structural assumptions, we reformulate the global safety condition into a scalable form that can be directly incorporated into the neural network loss. This enables the enforcement of overall system safety during local training. The experimental results demonstrate the effectiveness and scalability of the proposed method.

0.22

Invariance is Compositional for Continuous-time Systems: From Sleekness to Lebesgue Density

eess.SY ·2026-09-29 ·Othman Cherkaoui Dekkaki, Sadek Belamfedel Alaoui, Olayo Reynaud, Mohamed Maghenem, Alessio Iovine +1 more
unusual similarity 0.48
Abstract

This work establishes the first bidirectional compositional invariance result: robust forward invariance of a global Cartesian product set is shown to be equivalent to robust forward invariance of each local subsystem under coupling inputs from its neighbors. To facilitate this, we introduce the notion of tangential Lebesgue-density, a new condition that is weaker than classical sleekness but sufficient to ensure that the product of individual tangent cones equals the tangent cone of the product set. This equivalence reduces the curse of dimensionality by allowing the verification of a high-dimensional global system to be decomposed into a series of local sub-checks. The framework's scalability is demonstrated through a DC microgrid numerical example, confirming that the verification complexity grows only linearly with the number of subsystems.

0.26