This week on Journal Club session Olga Tveretina will talk about her work on "Complexity of the Reachability and Mortality Problems for Hybrid Dynamical Systems",
The mortality problem for a given dynamical system S consists of determining whether every trajectory of S eventually halts. The mortality problem is relevant to the field of program termination, and it has been studied in different contexts and in different variants. Closely related to mortality is the reachability problem: does exist a trajectory starting at a given initial state which evolves to reach a given final state. Both problems are undecidable in general, and they are only decidable for a limited number of classes of hybrid dynamical systems.
My recent related work includes results on decidability of mortality and reachability for some hybrid dynamical systems on manifolds [1, 2]. The complexity of these problems has received less attention of the community than the fundamental issue of their decidability. Studying the computational complexity of the algorithms for deciding reachability and mortality problems presented in [1, 2] is one of my current research focuses.
In my talk I will discuss the computational complexity of reachability and mortality for the closely related systems, so-called Restricted Hierarchical Hybrid Systems. These models have been studied by P. Bell, Sh. Chen, and L. Jackson [3], and they are a useful tool for exploring the complexity of such problems for other kinds of systems.
While the current aims are to improve understanding the boundary between decidable and undecidable systems and their computational complexity, it is worth mentioning that hybrid dynamical systems on manifolds have important practical applications. Areas where surfaces arise include among others biological systems (modelling processes on cell membranes), robotics (the configuration space of a robotic arm) and learning algorithms (finding a low-dimensional parameterization of high-dimensional data).
Papers:
- M. de Oliveira Oliveira, O. Tveretina, "Mortality and Edge-to-Edge Reachability are Decidable on Surfaces, Hybrid Systems: Computation and Control", 2022
- A. Sandler, O. Tveretina, "Deciding Reachability for Piecewise Constant Derivative Systems on Orientable Manifolds, Reachability Problems", 2019
- P. Bell, Sh. Chen, and L. Jackson, "On the Decidability and Complexity of Problems for Restricted Hierarchical Hybrid Systems", Theoretical Computer Science, 2016
Date: 2022/03/11
Time: 14:00
Location: online