On this week's Journal Club session, Olga Tveretina will talk about her work in the presentation entitled "Complexity of Reachability and Mortality for Low-dimensional Dynamical Systems".
Theory of dynamical systems provides a powerful framework for understanding complex dynamics, and its applications span a wide range of fields, including biological systems.
The reachability problem involves determining whether a given state or configuration of a system can be reached from another state through a sequence of transitions or actions. It is a fundamental question in computer science and has numerous applications across various domains. Thus, reachability analysis applied in systems biology helps to model and analyze biological networks such as gene regulatory networks, protein interaction networks, and metabolic pathways.
The mortality problem can be stated as follows: given a dynamical system, is it the case that all trajectories of the system are mortal? The mortality problem is relevant to the field of program termination, and it has been studied in different contexts and in different variants.
In this talk, I will present my current work on the computational complexity of reachability and mortality for specific classes of low- dimensional dynamical systems. Areas where variations of such systems arise include, among others, biological systems (gene regulatory networks), robotics (the configuration space of a robotic arm), and learning algorithms (finding a low-dimensional parameterization of high-dimensional data).
Papers:
- M. Oliveira, Oliveira, O. Tveretina, "Mortality and Edge-to-Edge Reachability are Decidable on Surfaces", 2022, Hybrid Systems: Computation and Control, 1--10
- P. Bell, S. Chen, L. Jackson, "On the decidability and complexity of problems for restricted hierarchical hybrid systems", 2016, Theoretical Computer Science, 652, 47--63
Date: 2024/04/19
Time: 14:00
Location: C258 & online