Breaking Dense Structures: Proving Stability of Densely Structured Hybrid Systems

Eike Möhlmann
(Carl von Ossietzky University of Oldenburg)
Oliver Theel
(Carl von Ossietzky University of Oldenburg)

Abstraction and refinement is widely used in software development. Such techniques are valuable since they allow to handle even more complex systems. One key point is the ability to decompose a large system into subsystems, analyze those subsystems and deduce properties of the larger system. As cyber-physical systems tend to become more and more complex, such techniques become more appealing.

In 2009, Oehlerking and Theel presented a (de-)composition technique for hybrid systems. This technique is graph-based and constructs a Lyapunov function for hybrid systems having a complex discrete state space. The technique consists of (1) decomposing the underlying graph of the hybrid system into subgraphs, (2) computing multiple local Lyapunov functions for the subgraphs, and finally (3) composing the local Lyapunov functions into a piecewise Lyapunov function. A Lyapunov function can serve multiple purposes, e.g., it certifies stability or termination of a system or allows to construct invariant sets, which in turn may be used to certify safety and security.

In this paper, we propose an improvement to the decomposing technique, which relaxes the graph structure before applying the decomposition technique. Our relaxation significantly reduces the connectivity of the graph by exploiting super-dense switching. The relaxation makes the decomposition technique more efficient on one hand and on the other allows to decompose a wider range of graph structures.

In Jun Pang, Yang Liu and Sjouke Mauw: Proceedings 4th International Workshop on Engineering Safety and Security Systems (ESSS 2015), Oslo, Norway, June 22, 2015, Electronic Proceedings in Theoretical Computer Science 184, pp. 49–63.
Published: 10th June 2015.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: