CS Paper Radar

Necessary and Sufficient Structural Conditions for the Validity of Lyapunov-Type Exponential Stability Criteria

Yixiang Guo, Lin Tie, Quan Quan

eess.SY ·submitted 2026-10-28 03:52 UTC · v1
theoryunusual

Abstract

Whether the exponential decay of a Lyapunov function along trajectories implies exponential stability of the state---an inference we call migration---is long assumed in Lyapunov's second method but never characterized at the criterion level. We formalize stability criteria over trajectory families, distinguish admissibility of a criterion (its structural condition suffices for its conclusion) from tightness (its necessity), and establish the necessary and sufficient structural conditions for validity. In logarithmic coordinates the theory reduces to a single two-sided displacement function of the comparison pair: in discrete time, migration holds if and only if a regularity package (excluding failure by infinitely many steps of finite displacement) and a joint lower bound (excluding failure by a single step of unbounded expansion) hold simultaneously. Continuous time strengthens the latter; the two criteria are separated exactly by the minimum step size. Written without its inverse-function formulation, the Panteley--Lor'ia criterion coincides with our continuous-time conditions on every nondecreasing pair, and loses soundness beyond: it was already complete on the classical regularity class. An envelope construction shows that regularization costs no discriminative power, and radial unboundedness, a standing assumption since Hahn, is dispensable.

Closest papers

Nearest neighbours by meaning across the whole index.

Sufficient and Necessary Smooth Barrier-Like Conditions for Continuous-Time Finite-Horizon Safety Verification

eess.SY ·2026-11-03 ·Bai Xue
similarity 0.53
Abstract

We study finite-horizon safety verification for continuous-time stochastic systems modeled by stochastic differential equations. Given an open and bounded safe set, a compact initial set, a finite time horizon, and a prescribed violation-probability threshold, the objective is to certify that the exit probability from the safe set before the horizon remains below the threshold. Under uniform ellipticity of the diffusion matrix and regularity of the safe-set boundary, we develop a time-dependent barrier-like condition expressed as a set of functional inequalities, obtained by relaxing a parabolic initial-boundary value problem associated with the exit probability. If a function satisfies the condition, then the probability of leaving the safe set before the horizon is guaranteed to remain below the threshold. Conversely, when the exit probability is strictly smaller than the prescribed threshold uniformly over the initial set, the barrier-like condition is also necessary: there exists a smooth function satisfying it. Furthermore, when the dynamics are polynomial and the set descriptions are semialgebraic, the problem of verifying the condition admits a sum-of-squares formulation that is both sound and complete, yielding a complete degree hierarchy for finite-horizon stochastic safety verification.

0.21

PSPACE-Completeness of the Reachability Relation of Robust Dynamical Systems

cs.CC ·2026-10-19 ·Manon Blanc
theory similarity 0.52
Abstract

Dynamical systems are a widely used model of computation and an intuitive representation of many natural phenomena in many applied fields. The last decades have seen an impressive use of computers in studying and analysing them, with several visible theoretical breakthroughs. The question of reachability for dynamical systems is central: given two points, is there a trajectory between them in the dynamical system? Reachability, in particular over the reals, is undecidable in the general case: it is only computably enumerable, even under reasonable hypotheses, e.g. for a computable dynamics in general. But it is known to become decidable, and even lies in PSPACE, under suitably quantified robustness assumptions. In this paper, we focus on PSPACE-completeness results over the reals, in the sense of computable analysis, regarding discrete-time and continuous-time robust dynamical systems. We prove that, under some additional and rather reasonable hypotheses, the reachability relation becomes even PSPACE-complete for both classical and second-order complexity second-order complexity, for an adapted notion of reduction. As a side-effect, we also prove an improvement of an algebraic Ordinary Differential Equations-based characterisation of PSPACE, removing one of the base functions of the algebra. By doing so, we link results from dynamical systems and complexity over the reals, including the models of computable analysis and second-order complexity.

0.29

Algebraic Characterization of Time-Varying Set Invariance

eess.SY ·2026-11-02 ·S. B. Alaoui, E. J. Wafo Wembe, A. Saoud
publishedtheory similarity 0.51
Abstract · The paper was accepted for publication in the CDC 2026

The verification of temporal forward invariance for dynamical systems subject to time-varying constraints is a foundational problem in the analysis of safety-critical systems. Existing methodologies rely on restrictive geometric assumptions, such as the Linear Independence Constraint Qualification (LICQ), or suffer from exponential computational complexity when applied to time-varying polytopes. This paper establishes a rigorous, unified, and computationally tractable framework for temporal safety verification. First, utilizing tools from nonsmooth analysis, we prove that a Nagumo-type geometric inclusion evaluated strictly on the boundary of the augmented graph is both necessary and sufficient for temporal forward invariance. Second, we provide an algebraic characterization of this condition requiring only the weaker Abadie Constraint Qualification (ACQ), generalizing standard Control Barrier Function (CBF) boundary conditions to non-smooth, multi-constraint domains. Finally, for the practical class of Linear Time-Invariant (LTI) systems with time-varying polytopic constraints, we deploy Farkas' Lemma to eliminate exponential vertex enumeration. By introducing a Lipschitz-bounded time-discretization scheme, we reduce the infinite-dimensional continuous-time verification problem to a finite, highly tractable set of decoupled Linear Programs (LPs).

0.39

Sufficient and Necessary Continuous Barrier-like Conditions for Discrete-Time Stochastic Reach-Avoid Verification

eess.SY ·2026-09-21 ·Bai Xue
similarity 0.49
Abstract

This paper develops necessary and sufficient barrier-like characterizations using continuous barrier functions for infinite-horizon reach-avoid verification of discrete-time stochastic systems. Existing results establish necessary and sufficient conditions in terms of functional inequalities involving measurable or lower semicontinuous barrier functions. However, the limited regularity of such functions may hinder their numerical approximation and computational synthesis. Building on our previous barrier-like condition for finite-horizon reach-avoid verification, we show that this condition can also be used for infinite-horizon reach-avoid verification and, under a uniform absolute continuity condition on the transition kernels, admits a continuous barrier function whenever the exact reach-avoid probability is strictly larger than the prescribed threshold for every state in the initial set. We further show that the resulting continuous barrier function can be uniformly approximated by a polynomial one while preserving the required barrier-like conditions. For polynomial systems, we formulate these conditions as polynomial positivity constraints over compact basic semialgebraic sets. Putinar's Positivstellensatz then converts the positivity conditions into sum-of-squares (SOS) certificates, yielding semidefinite programming (SDP) formulations for synthesizing polynomial barrier functions. We establish both soundness and completeness of the resulting SOS-based procedure. Finally, two numerical examples illustrate the theoretical results and demonstrate the resulting SDP approach.

0.34

Quantitative Reachability Properties Beyond Decisiveness

cs.LO cs.FL ·2026-10-26 ·Raphaël Faure, Alain Finkel, Lina Ye
similarity 0.49
Abstract · 38 pages

Decisiveness is central to reachability algorithms for infinite Markov chains, but is a qualitative notion: it guarantees that path-enumeration algorithms terminate, without an a priori bound on the horizon. We study decisiveness quantitatively of Markov chains, and apply our results to the approximate quantitative coverability problem for effective probabilistic well-structured transition systems (pWSTS). We introduce truncation sets, which represent the horizons sufficient to approximate the reachability probability within a precision $\varepsilon$. These sets reformulate decisiveness quantitatively, and their elements can be computed when it is decisive. To obtain such horizons, before any exploration, we introduce geometrically reachable sets, for which the probability of not reaching them within n steps decreases exponentially in n, up to a prefactor depending on the initial state. Horizons valid for all initial states exist iff this prefactor can be chosen uniformly for boundedly coarse chains. For such pWSTS, including probabilistic vector addition systems and Galton-Watson processes, we obtain a priori global horizons growing at most logarithmically in $1/\varepsilon$. In the non-uniform case, we give a drift condition ensuring the existence of a finite geometrically reachable set. Under this condition, we derive a priori horizons growing at most logarithmically in $1/\varepsilon$ and in the weight w(x) measuring the size of the initial state x. In both cases, we compute a horizon function whose evaluation on any initial state and precision requires only a constant number of elementary operations $(+, -, \times, / \text{ and } \log)$. For probabilistic lossy channel systems, this yields, to our knowledge, the first explicit a priori horizons from arbitrary initial states, and it extends to $ν$-pLCS, a new infinitely branching variant with probabilistic emissions.

0.23

Construction of Control Lyapunov-Barrier Functions from CLF-CBF Pairs

eess.SY ·2026-09-10 ·Bo Wang, Miroslav Krstic
similarity 0.48
Abstract

This paper studies the construction of control Lyapunov-barrier functions (CLBFs) from a given control Lyapunov function (CLF) $V$ and control barrier function (CBF) $h$. We consider functions of the form $W=F(V,h)$ that increase with the CLF value and do not increase with the barrier value, and show that the CLBF decrease condition is completely characterized by a nonnegative scalar weight that governs the relative contributions of the CLF and CBF. Because this weight depends only on $(V,h)$, the same value must satisfy the decrease condition at all states sharing the same CLF and CBF values, which leads to a joint-level-set admissibility condition. We then construct CLBFs from admissible weights through a first-order partial differential equation (PDE) and obtain explicit multiplicative and power-type families as special cases. We further identify an integrability obstruction showing that admissibility alone does not guarantee properness. Two nonlinear examples illustrate the constructions and demonstrate safe stabilization in cases where feedback based on the original CLF violates the safety constraint.

0.29

Converse Barrier Certificates for Set-Based Stochastic Reach-Avoid Verification

eess.SY ·2026-08-31 ·Bai Xue, C. -H. Luke Ong
similarity 0.46
Abstract

Recent work established sufficient and necessary barrier-like conditions for infinite-horizon reach-avoid verification of stochastic discrete-time systems from a single initial state. Whether such a converse characterization extends to a set of initial states, however, remains open. In this paper, we answer this question affirmatively for compact initial sets. We consider a uniform reach-avoid specification requiring the reach-avoid probability to exceed a prescribed threshold for every initial state in a compact set. Under appropriate assumptions, including continuous system transitions, together with a strict uniform probability margin, we extend the pointwise converse characterization to the uniform setting.

0.42

Input-to-State Safety and Small-Gain Theorems for Large-Scale Nonlinear Systems

eess.SY ·2026-11-10 ·Jianqiang Wang, Tengfei Liu, Zhong-Ping Jiang
theory similarity 0.46
Abstract · 16 pages, 7 figures

This paper studies the safety verification problem for a general class of large-scale systems characterized by multiple safety indicator functions. Each safety indicator function satisfies a trajectory-based input-to-state safety (ISSf) estimate that provides a lower bound on its value along system trajectories in terms of the initial state, external inputs, and the other safety indicator functions, whose influence is quantified by continuous and nondecreasing gain functions. Within this framework, we establish a safety-oriented small-gain theorem and its corresponding corollaries that enable compositional and scalable safety verification of the interconnected system, provided that the interconnection gain functions satisfy a small-gain condition on the negative real axis. This condition concerns only the neighborhood of the safety boundary, thereby facilitating the application of our results to safety verification of multi-agent systems under distributed control. Our proof combines small-gain techniques with the lower-bound structure of ISSf estimates and develops an inductive comparison argument that establishes the ISSf property for the overall system throughout the maximal interval of existence. As an application, we establish robust safety for the natural distributed "half-spring" controller, theoretically supporting the computationally efficient and inspiring approach to safety-critical control of multi-agent systems in the presence of obstacles and external disturbances.

0.23